mario::konrad
programming / C++ / sailing / nerd stuff
Algorithm: Shell Sort
© 2005 / Mario Konrad

Description

Sorting of h parts in distance of the elements of h. Merging the parts for descending order of h values with insertion sort. This means the elements gets moved over a greater distance. Typical: h(k+1)=3*h(k)+1h(k+1) = 3 * h(k) + 1

Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int h = 1;
while (h <= array.count()) {
    h = 3*h+1;
}

while (h > 0) {
    h = h / 3;

    for (int i = (h-1); i < array.count(); ++i) {
        int j = i;
        while ((j > h-1) && (array[j] < array[j-h-1])) {
            array.swap( j-h-1, j );
            j = j - h - 1;
        }
    }
}

Analysis

Asymptotic complexity depends on h:

For h(k+1)=3*h(k)+1h(k+1) = 3 * h(k) + 1:

Mavg=1.29*n1.28M_{avg} = 1.29 * n^1.28

Cavg=O(n3/2)C_{avg} = O( n^3/2 )

For h(k+1)=2*h(k)h(k+1) = 2 * h(k):

Mavg=O(n3/2)M_{avg} = O( n^3/2 )

Cavg=O(n3/2)C_{avg} = O(n^3/2)

For h=2p*3q...,16,12,9,8,6,4,3,2,1h = 2^p * 3^q {..., 16, 12, 9, 8, 6, 4, 3, 2, 1}:

Mavg=O(n*log2(n))M_{avg} = O(n * log^2(n))

For h=floor(n*α),floor(floor(n*α)*α),...,1h = floor(n * \alpha), floor(floor(n * \alpha) * \alpha), ..., 1:

Mavg=1.75*n1.19M_{avg} = 1.75 * n^1.19