Analysis of Modified Heap Sort Algorithm on Different Environment

Authors: Vandana Sharma, Parvinder S. Sandhu, Satwinder Singh, Baljit Saini

Abstract:

In field of Computer Science and Mathematics, sorting algorithm is an algorithm that puts elements of a list in a certain order i.e. ascending or descending. Sorting is perhaps the most widely studied problem in computer science and is frequently used as a benchmark of a system-s performance. This paper presented the comparative performance study of four sorting algorithms on different platform. For each machine, it is found that the algorithm depends upon the number of elements to be sorted. In addition, as expected, results show that the relative performance of the algorithms differed on the various machines. So, algorithm performance is dependent on data size and there exists impact of hardware also.

Keywords: Algorithm, Analysis, Complexity, Sorting.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1082603

References:

[1] Knuth D E. The Art of Programming-Sorting and Searching. 2nd edition Addison Wesley.
[2] Thomas H, Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 2nd edition, MIT Press, Cambridge, May 2001, Chap. 7.
[3] Hoare C A R. Quicksort. Computer Journal, 5(1):10-15.
[4] Floyd R W. Algorithm 245: Treesort 3. Communications of ACM, 1964, 7(4): 701.
[5] Williams J W J. Algorithm 232: HEAPSORT. Communications of ACM, 1964, 7(4): 347-348.
[6] Cormen et al. Introduction to Algorithms, Chap. 6.
[7] I.Wegner: BOTTOM-UP-HEAPSORT beating on average QUICKSORT (if n is not very small). Proceedings of the MFCS90, LNCS 452: 516-522, 1990
[8] Wegner I. The Worst Case Complexity of McDiarmid and Reed-s Variant of BOTTOM-UP HEAP SORT. Information and computation, 1992, 97(1): 86-96.
[9] S.Carlsson: A variant of HEAPSORT with almost optimal number of comparisons. Information Processing Letters, 24: 247-250, 1987.
[10] I.Wegner: The worst case complexity of Mc diarmid and Reed's variant of BOTTOM-UP-HEAP SORT. Proceedings of the STACS91, LNCS 480: 137-147, 1991.
[11] Xio Dong Wang, Ying Jie Wu. An improved heap sort algorithm with nlogn -0.788928n comparisons in worst case. Journal of Computer Science and Technology. 22(6): 898-903.
[12] Gonnet G H, Munro J I. Heaps on Heaps. SIAM Journal on Computing, 1986, 15(6): 964-971.
[13] McDiarmid C J H, Reed B A. Building Heaps Fast. Journal of Algorithms, 1989, 10(3): 352~365.
[14] Dutton R D. Weak Heap Sort. BIT, 1993, 33(3): 372-381.
[15] Edelkamp A S, Stiegeler P. Implementing HEAPSORT with nlogn - .0n and QUICKSORT with nlogn+0.2n comparisons. ACM journal Of Experimental Algorithmics (JEA), 2002, 7(1): 1-20.
[16] Cantone D, Cincotti G. QuickHeapsort: an efficient mix of classical sorting algorithms. Theoretical Computer Science 2002, 285(1): 25-42.
[17] Carlsson S, Chen J. The Complexity of Heaps. The Third Annual ACM SIAM symposium on Discrete Algorithms, SIAM, Philandelphia, PA, October 1992, pp 393-402.
[18] Ding Y, Weiss M A. Best Case Lower Bounds for Heap Sort. Computing, 1992, 49(1): 1-9.
[19] Z LiBruce A. REEd: Heap Building Bounds. LNCS, 2005, 3608(1): 14- 23.
[20] Reinhard K. Sorting in Place with a Worst Case Complexity of nlogn- 1.3n + O(logn) comparisons and nlogn+O(1) transports. LNCS, 1992, 650(6): 489-499.