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"

Type

Adaptive
Stable
In-Place

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

shellsort.JPG

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;
            }
         }
 
      }
   }
 
}