Indexed by:
Abstract:
A new variant of HEAPSORT is presented in this paper. The algorithm is not an internal sorting algorithm in the strong sense, since extra storage for n integers is necessary. The basic idea of the new algorithm is similar to the classical sorting algorithm HEAPSORT, but the algorithm rebuilds the heap in another way. The basic idea of the new algorithm is it uses only one comparison at each node. The new algorithm shift walks down a path in the heap until a leaf is reached. The request of placing the element in the root immediately to its destination is relaxed. The new algorithm requires 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 more than necessary. It beats on average even the clever variants of QUICKSORT, if n is not very small. The difference between the worst case and the best case indicates that there is still room for improvement of the new algorithm by constructing heap more carefully.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
ISSN: 1000-9000
CN: 11-2296/TP
Year: 2007
Issue: 6
Volume: 22
Page: 898-903
0 . 4 4 1
JCR@2007
1 . 2 0 0
JCR@2023
ESI Discipline: COMPUTER SCIENCE;
JCR Journal Grade:3
Cited Count:
WoS CC Cited Count: 3
SCOPUS Cited Count: 7
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: