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.


cover contents index main page

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.

mail