An Improved HEAPSORT Algorithm with n log n - 0.788928n Comparisons in the Worst Case

Xiao-Dong Wang; Ying-Jie Wu

Volume 22 Issue 6

November 2007

Turn off MathJax

Article Contents

Abstract

References

Journal of Computer Science and Technology > 2007 > 22(6): 898-903.

Xiao-Dong Wang, Ying-Jie Wu. An Improved HEAPSORT Algorithm with n log n - 0.788928n Comparisons in the Worst Case[J]. Journal of Computer Science and Technology, 2007, 22(6): 898-903.

Citation:

Xiao-Dong Wang, Ying-Jie Wu. An Improved HEAPSORT Algorithm with n log n - 0.788928n Comparisons in the Worst Case[J]. Journal of Computer Science and Technology, 2007, 22(6): 898-903.

Citation:

Xiao-Dong Wang, Ying-Jie Wu. An Improved HEAPSORT Algorithm with n log n - 0.788928n Comparisons in the Worst Case[J]. Journal of Computer Science and Technology, 2007, 22(6): 898-903.

Previous Article Next Article

An Improved HEAPSORT Algorithm with n log n - 0.788928n Comparisons in the Worst Case

College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350002, China

More Information

Received Date: September 29, 2006
Revised Date: May 07, 2007
Published Date: November 14, 2007

Abstract

Abstract

A new variant of HEAPSORT is presented in this paper. The algorithm is not an internalsorting algorithm in the strong sense, since extra storage for $n$ integers is necessary. The basic idea of the new algorithm is similar tothe classical sorting algorithm HEAPSORT, but the algorithm rebuilds theheap in another way. The basic idea of the new algorithm is it uses onlyone comparison at each node. The new algorithm shift walks down a path inthe heap until a leaf is reached. The request of placing the element inthe root immediately to its destination is relaxed. The new algorithmrequires about $n \log n-0.788928n$ comparisons in the worst case and $n\log n-n$ comparisons on the average which is only about $0.4n$ morethan necessary. It beats on average even the clever variants ofQUICKSORT, if $n$ is not very small. The difference between the worstcase and the best case indicates that there is still room forimprovement of the new algorithm by constructing heap more carefully.
- data structures,
- analysis of algorithms,
- heaps,
- HEAPSORT

FullText(HTML)

References (16)

References

[1]	Knuth D E. The Art of Computer Programming --Sorting } and Searching. 2nd Edition, New York: Addison Wesley, 1998.
[2]	Floyd R W. Algorithm 245: Treesort 3. -\it Communications of the ACM}, 1964, 7(4): 701.
[3]	Williams J W J. Algorithm 232: HEAPSORT. -\it Communications of the ACM}, 1964, 7(4): 347 $\sim$ 348.
[4]	Wegener I. BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT, beating on an average, QUICKSORT (if $n$ is not very small). -\it Theoretical Computer Science}, 1993, 118(1): 81 $\sim$ 98.
[5]	Carlsson S. A variant of HEAPSORT with almost optimal number of comparisons. -\it Information Processing Letters}, 1987, 24(3): 247 $\sim$ 250.
[6]	Wegener I. The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than $n\log n + 1.1n$ . -\it Information and Computation}, 1992, 97(1): 86 $\sim$ 96.
[7]	Gonnet G H, Munro J I. Heaps on heaps. -\it SIAM Journal on Computing}, 1986, 15(6): 964 $\sim$ 971.
[8]	McDiarmid C J H, Reed B A. Building heaps fast. -\it Journal of Algorithms}, 1989, 10(3): 352 $\sim$ 365.
[9]	Hoare C A R. Quicksort. -\it Computer Journal}, 5(1): 10 $\sim$ 15.
[10]	Dutton R D. Weak heap sort. -\it BIT}, 1993, 33(3): 372 $\sim$ 381.
[11]	Edelkamp S, Stiegeler P. Implementing HEAPSORT with $n \log n 0.9n$ and QUICKSORT with $n \log n + 0.2n$ comparisons. -\it ACM Journal of Experimental Algorithmics $($ JEA $)$ }, 2002, 7(1): 1 $\sim$ 20.
[12]	Cantone D, Cincotti G. QuickHeapsort, an efficient mix of classical sorting algorithms. -\it Theoretical Computer Science}, 2002, 285(1): 25 $\sim$ 42.
[13]	Carlsson S, Chen J. The complexity of heaps. In -\it Proc. the Third Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM}, Philadelphia, PA, October 1992, pp.393 $\sim$ 402.
[14]	Ding Y, Weiss M A. Best case lower bounds for Heapsort. -\it Computing}, 1992, 49(1): 1 $\sim$ 9.
[15]	Z Li, Bruce A Reed. Heap building bounds. -\it LNCS}, 2005, 3608(1): 14 $\sim$ 23.
[16]	Reinhardt K. Sorting in place with a worst case complexity of $n\log n 1.3n + O(\log n)$ comparisons and $\varepsilon n\log n + O(1)$ transports. -\it LNCS}, 1992, 650(6): 489 $\sim$ 499.

Relative Articles

[1]	JIANG Tao, LI Ming, Paul M.B. Average-Case Analysis of Algorithms Using Kolmogorov Complexity[J]. Journal of Computer Science and Technology, 2000, 15(5): 402-408.
[2]	LUO Jianhua, ZHUANG Tiange. Reduction of Artifacts in Images from MR Truncated Data Using Singularity Spectrum Analysis[J]. Journal of Computer Science and Technology, 2000, 15(4): 360-367.
[3]	LI Jianzhong, LI Yingshu, Jaideep Srivastava. Efficient Aggregation Algorithms on Very Large Compressed Data Warehouses[J]. Journal of Computer Science and Technology, 2000, 15(3): 213-229.
[4]	Ding Wei, Gong Jian, Yu Xiao. A Traffic Partition Algorithm for Switched LANs and Its Performance Analysis[J]. Journal of Computer Science and Technology, 1998, 13(3): 261-267.
[5]	Guan Jiwen, D.A.Bell. General Algorithms for Barnett s Structure in Evidential Reasoning[J]. Journal of Computer Science and Technology, 1995, 10(6): 518-535.
[6]	Wu Jigang, Zhu Hong. The Least Basic Operations on Heap and Improved Heapsort[J]. Journal of Computer Science and Technology, 1994, 9(3): 261-266.
[7]	Zheng Fangqing. A Common Reasoning Model and Its Application in Knowledge-Based System[J]. Journal of Computer Science and Technology, 1991, 6(1): 59-65.
[8]	Zheng Chongxun, Zhang Kenong. Orthogonal Algorithm of Logic Probability and Syndrome-Testable Analysis[J]. Journal of Computer Science and Technology, 1990, 5(2): 203-209.
[9]	Ye Daxing. Three Improvements on an Incremental Algorithm for Automatic Semantic Analysis[J]. Journal of Computer Science and Technology, 1989, 4(1): 67-74.
[10]	Pan Yangsheng. An Analysis of WS and PFF Algorithms[J]. Journal of Computer Science and Technology, 1987, 2(2): 145-156.

Supplements (0)

Cited By

Get Citation

XML

Article views (24) PDF downloads (6747)

Indexed in:

An Improved HEAPSORT Algorithm with n log n - 0.788928n Comparisons in the Worst Case

Abstract

References

Related Articles

Catalog

Related

Home

Overview

Resources

Contents

Indexed in:

An Improved HEAPSORT Algorithm with n log n - 0.788928n Comparisons in the Worst Case

Abstract

References

Related Articles

Catalog

Related

Home

Overview

Resources

Contents

Export File

Citation

Format

Content