Analysis of Modified Heap Sort Algorithm on Different Environment

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.

Authors:

• Vandana Sharma
• Parvinder S. Sandhu
• Satwinder Singh
• Baljit Saini

Keywords:

• Algorithm
• Analysis
• Complexity
• Sorting.

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.