The problem with the simple sorts Selection, Insertion, and Bubble sort is that they only compare and swap adjacent elements.
Theorem 1. Any algorithm the sorts an n-element list only by comparing and swapping adjacent elements must do at least n(n - 1)/2 comparisons in the worst case and at least n(n - 1)/4 comparisons on average.
So to beat the O(n2) time bound, we must be able to compare and move elements that are farther apart. Shellsort (named for its inventor, Donald Shell) works by sorting evenly spaced sublists intermingled through the entire list. The sublists are determined by a sequence of increments hk, hk-1, hk-2, . . . h1. Suppose for example that the first increment hk is 6. Then each sublist will consists of every 6'th element - there are 6 such sublists starting with the first 6 elements. After these sublists are sorted, the next increment is used to divide the list up into sublists. This process is repeated for each increment; the final increment is always 1 so that at the end the entire list will be sorted.
What algorithm should be used to sort the sublists? Considering that the last increment is 1 and that the entire list is sorted on this pass, is Shellsort any more efficient than the algorithm used to sort the sublists? Call a list h-ordered if all the sublists consisting of every h'th element is in sorted order. To k-sort a list means to sort the sublists using increment k
Theorem 2. If an h-ordered list is k-sorted, then it will remain h-ordered.
What this means is that the work performed during one increment does not undo any of the work done for the previous increments. Now consider the following example.
initial list: 7 19 24 13 31 8 82 18 44 63 5 29
list after sorting on increment 6: 7 18 24 13 5 8 82 19 44 63 31 29
list after sorting on increment 4: 5 8 24 13 7 18 31 19 44 63 82 29
list after sorting on increment 3: 5 7 18 13 8 24 31 19 29 63 82 44
list after sorting on increment 2: 5 7 8 13 18 19 29 24 31 44 82 63
list after sorting on increment 1: 5 7 8 13 18 19 24 29 31 44 63 82
Notice the in the final passes, few elements are out of order and not very far out of order. The only changes made in the final pass are to swap two pairs of adjacent elements. Hence to be efficient, we need to use a sort that is efficient when the list is almost sorted. Insertionsort has this property (it is linear on an already sorted list).
Can we write this algorithm using insertionsort in a way that minimizes the bookkeeping needed to keep track of the sublists? Yes! We can avoid the extra bookkeeping by having the program make one pass through the entire list for each increment, intermingling the work on all the sublists. The only change we need to make to insertionsort is to change the 1s to hs where h is the current increment.
void insertion( int a[] )
{
for (int i = 1; i < a.length; i++)
{
int v = a[i];
int j = i-1;
for (; j >= 0 && a[j] > v; j -= 1)
a[j+1] = a[j];
a[j+1] = v;
}
}
void shell( int a[] )
{
// let h iterate over the increments
for (int i = h; i < a.length; i++)
{
int v = a[i];
int j = i-h;
for (; j >= 0 && a[j] > v; j -= h)
a[j+h] = a[j];
a[j+h] = v;
}
}
So what increment sequence should we use? Using the increments that are one less than the powers of 2 (1, 3, 7, 15, 31, 63,), the worst case number of comparisons is O(n3/2 ) so shellsort can beat selection, insertion, and bubble sort.
How well can shellsort perform on the average? Unfortunately, the average case is unknown for every practical increment sequence. The question of which increment sequence to use can only be determined empirically which is the purposes of this week's programming assignment. As it turns out, shellsort performs excellently with a good increment sequence even up to several thousand elements. Hence, it makes an excellent default sorting algorithm. You only need to use the more complicated mergesort and quicksort when you need to sort 10s or 100s of thousands of elements.
If the increment sequence does not depend on the number of array elements, they can be precomputed and placed in array as in the following code.
int h[6] = {364, 121, 40, 13, 4, 1};
for (int k=0; k < h.length; k++)
// the current increment is h[k]
If the increment sequence depends on the size of the array being sorted, then we can't precompute them but this is not a problem. An example of such a sequence for an array of N elements is as follows.
for (int h = 5*N / 11; h > 0; h = (h == 2) ? 1 : 5*h/11)
// the current increment is h
You may be unfamiliar with the kind of expression used in the increment part of the the preceding for-loop. The expression behaves like an if-statement but syntactically you can use it anyplace where can use a value or expression.
Syntax of the Ternary ? : operator
? :
The? and: are required parts of syntax. The <...> items are placeholder's containing a term that describes what should go there. The above is syntactically an expression. Its meaning is as follows. The condition is evaluated. If it evaluates to true, then the value of the expression is whatever the evaluates to. Otherwise (the condition is false), the value of the expression is whatever the evaluates to. So if h is 2, then the value of the expression is 1 and this gets assigned as the new value of h. Otherwise, the new value of h is the value of 5 * h/11. The reason we need the special case is that when h is 2, the value of 5 * h/11 is 0 due to integer division. The outer loop would then terminate without the increment ever becoming 1 as required.
Java gets the ternary operator from C (Java is based on C). Strictly speaking, it is not a necessary part of the language and it isn't used very often but in this case, it seems the cleanest way to write the code.