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 n^{th} element is sorted.

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

## Type

## Complexity

Complexity depends on the jumps you pick; with a jump of 1 the worst case is O(n^{2}).

However if the jumps are picked well the worst case is O(nln^{2}(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