Shellsort

Shellsort

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

We first sort all elements that are at distance H.1 from each other, then re-sort the array using increment H.2, finally we do an ordinary insertion sort with increment 1 (H.1>H.2>...>1). D. L. Shell, the originator of the algorithm, took H=N%2 as the first value of H and used the formula H=H%2. A sequence which has been shown empirically to do well is
H=...,1093,364,121,40,13,4,1
i.e H=(3**K-1)/2 which can be generated by the formula H=3*H+1 with the initial value H=1. The number of operations required in all is of order O(N**(3/2)) for the worst possible ordering of the original data. In average the operations count goes approximately as O(N**1.25).

PRACTICE

The following table compares four sorting algorithms. The A. array includes integers in the range 1 to Max=10,100,1000,40000.

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

SHELLSORT: procedure expose A.
parse arg N
H = 1
do until H > N; H = 3 * H + 1; end
do until H = 1
  H = H % 3
  do I = H + 1 to N
    V = A.I; J = I; JmH = J - H
    do while A.JmH > V
      A.J = A.JmH; J = J - H
      if J <= H then leave
      JmH = J - H
    end
    A.J = V
  end
end
return

CONNECTIONS

Sorting Problem
     Counting sort
     Heapsort
     Quicksort
Merging

Literatura
Rich R. P. Internal Sorting Methods Illustrated with PL/1 Programs

Prentice Hall, Inc., Engelwood Cliffs, 1972

Sedgewick R. Algorithms

Addison-Wesley, Reading, Massachusetts, 1984

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.