COMP1927 - Shell Sort

Shell Sort is a variant of insertion sort, that works by sorting the list multiple times (with a different n), so that every nth element is sorted.

The best known sequence is "1750, 701, 301, 132, 57, 23, 10, 4, 1"

## Complexity

Complexity depends on the jumps you pick; with a jump of 1 the worst case is O(n2).

However if the jumps are picked well the worst case is O(nln2(n)) (so best worst case).

The best case is O(n), when everything is pre-sorted.

## Example ## Code

```void shellSort (int array[], int length, int jumps[], int numJumps) {

int i;

for (i = 0; i < numJumps; i++) {
nInsertionSort(array, length, jumps[i]);
}

}

void nInsertionSort (int array[], int length, int jump) {

int placed = FALSE;

int temp;

int i;
int k;
int startPoint;

// Start your jump-sort from each of the first jump elements
// This will then cover all elements
// E.g. jump = 5, starting at 0 gets multiples of 5
//1 gets multiples of 5 remainder 1...etc
for (startPoint = 0; startPoint < jump; startPoint++) {
// From each startpoint, sort all jump^^th^^ elements
for (i = startPoint; i < length; i+=jump) {
placed = FALSE;
// While the element hasn't been placed correctly
// Compare to the previous jump^^th^^ element
for (k = i-jump; ((k >= 0) && (!placed)); k-=jump) {
// If the element needs swapping, swap it
// Then adjust i to mark where it is currently at
if (array[i] < array[k]) {
temp = array[i];
array[i] = array[k];
array[k] = temp;
i = k;
} else {
placed = TRUE;
}
}

}
}

}
```
page revision: 7, last edited: 21 Aug 2011 03:46