Heapsort

Heapsort

PROBLEM

Given an array A. of N elements the result of sorting the array in place is to arrange elements of A. so that
A.1<=A.2<=...<=A.N

ALGORITHM

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.

PRACTICE

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.

Running time in seconds for N=10000
Algorithm Max = 100 Max = 1000 Max = 40000 Max = 99999

QUICKSORT 4.66 4.53 4.89 4.59

HEAPSORT 10.26 10.67 11.58 11.18

SHELLSORT 7.45 8.89 10.58 10.13

COUNTING_SORT 1.88 1.95 7.93 31.85

IMPLEMENTATION

Unit: nonrecursive internal subroutine

Global variables: array A. of arbitrary elements

Parameter: a positive integer N - number of elements in A.

Result: Reordering of input array such that
A.1<=A.2<=...<=A.N

HEAPSORT: procedure expose A.
parse arg N
do I = N % 2 to 1 by -1
  call SIFT I, N
end
do I = N to 2 by -1
  W = A.1; A.1 = A.I; A.I = W
  call SIFT 1, I - 1
end
return

SIFT: procedure expose A.
parse arg L, R
I = L; W = A.I; J = 2 * I
Jp1 = J + 1
if J < R then
  if A.J < A.Jp1 then J = Jp1
do while J <= R
  if W >= A.J then leave
  A.I = A.J; I = J; J = 2 * I
  Jp1 = J + 1
  if J < R then
    if A.J < A.Jp1 then J = Jp1
end
A.I = W
return

CONNECTIONS

Sorting Problem
     Counting sort
     Shellsort
     Quicksort
Merging

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.

Modification of HEAPSORT
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.