Heapsort by J. W. J. Williams is a sorting algorithm in place whose worst-case running time is O(N*lgN) on an input array of N items.
A good implementation of
QUICKSORT usually beats
HEAPSORT in practice. On average the number of comparisons done in
HEAPSORT is about twice as much as in
QUICKSORT, but
HEAPSORT avoids the slight possibility of a catastrophic degradation of performance. The following table compares four sorting algorithms. The
A. array includes integers in the range
1 to
Max=100,1000,40000,99999.
CONNECTIONS
Literature
Wirth N. Algorithms and data structure
New Jersey, Prentice Hall, Inc., Engelwood Cliffs, 1986
Acknowledgement
I changed the test from Max=10 ... 40000 to Max=100 ... 99999. Thanks for idea go to Walter Pachl.
Note
This test ran in the Windows 2000 Professional environment on the computer with 132MB RAM and processor x86Family 6 Mode 6 Stepping 5.
James Barbetti sent me the HEAPSORT_RADIX3 subprogram written in Visual Basic. His comment follows:
Instead of ~ 2*N*log(N)/log(2) comparisons and moves
you get ~ 2*log(N)/log(3) + 2*N comparisons on average; and
~ N*log(N)/log(3) + N moves on average
HEAPSORT_RADIX3: procedure expose A.
parse arg N
do R = (N+1)%3 to 1 by -1
call SiftDown A.R, N, R
end
do R = N to 2 by -1
V = A.R; A.R = A.1
call SiftDown V, (R - 1), 1
end
return
SIFTDOWN: procedure expose A.
V = ARG(1); Count = ARG(2); I = ARG(3)
J = I
do forever
K = J * 3 - 1
if K < Count - 1
then do
Kp1 = K + 1; Kp2 = K + 2
if A.K < A.Kp1 then
if A.Kp1 < A.Kp2 then K = Kp2
else K = Kp1
else if A.K < A.Kp2 then K = Kp2
end
else do
if K < Count
then do
Kp1 = K + 1
if A.K < A.Kp1 then K = Kp1
end
else if Count < K then leave
end
A.J = A.K
J = K
end
K = J
do while K > I
J = (K + 1) % 3
if A.J > V then leave
A.K = A.J
K = J
end
A.K = V
return
|
Acknowledgement
Thanks for interesting (more theoretically) code go to James Berbetti.