trypots.nethomeShellsort
Shellsort is a interesting development from insertion sort that overcomes its main flaw. In insertion sort, a low number in a high position in the array may need to be moved a long way, but insertion sort can only perform exchanges with adjacent elements, which means it might take a large number of exchanges to get an element into its proper location. With shellsort, an ingenious solution has been devised. The array is divided into subarrays that are interleaved within the larger array. As the subarrays are sorted, the exchanges can be done on entries that are far apart. If the subarrays are arranged by taking every hth entry, then the array is said to be h-sorted. The basic idea is to start with a large value for h, h-sort the array, then incrementally reduce h so that the exchanges are increasingly made on entries that are nearer to each other. The last sweep resembles a regular insertion sort, but now on an array that has no exchanges far apart from each other.
My example program uses a 17 element array. shellsort is difficult to visualize at first, but its easy to describe its main effects. The sort begins with h set to 13. Thus, elements that are as far as 13 places apart may be exchanged. The sort makes four initial compares, a0 with a13, a1 with a14, a2 with a15, and a3 with a16. Only the last compare results in an exchange. After the first outer loop terminates, the 13-sorted array has 4 sorted sequences or subarrays of length 2: {a0, a13}, {a1, a14}, {a2, a15}, {a3, a16}. So far so good. We then decrement h so that it equals 4 and start again, this time aiming to produce a 4-sorted array. It's not really necessary to worry about the 13-sorted array that we just finished. It is as if we are starting over again. This time elements that are 4 places apart can be exchanged. Already this is starting to look a lot like a regular insertion sort, except now we know that no exchanges of elements far apart will happen. It's easy to imagine that if our original array was very large, and exchanges were made for elements hundreds or thousands of places apart, there would be a huge gain over insertion sort due to these types of exchanges being speeded up so much. So this time, when we have completed our 4-sorted array, we end up with 4 sorted subarrays: {a0, a4, a8, a12, a16}, {a1, a5, a9, a13}, {a2, a6, a10, a14}, {a3, a7, a11, a15}. Not only are these subarrays sorted, but they have the property that the largest element in each subarray is less than the smallest element in the next one. The last step is to create a 1-sorted array. Now we are doing what amounts to an insertion sort on the array, but the interleaved arrays are preventing then need to ever have to move an element more than 4 places. In this way, the savings over an insertion sort on the original unsorted array are immense. It is possible for shellsort to be 600 times faster than insertion sort!
I have tried just to give an overall picture here. I would refer interested readers to go to the section on shellsort in the book Algorithms by Robert Sedgewick and Kevin Wayne, or to visit their site at Princeton University Algorithms. They provide an excellent introduction, particularly on the reasons for setting the value for h as we have done here.
To quote briefly on some of their observations:
You will see that shellsort makes it possible to address sorting problems that could not be addressed with more elementary algorithms. This example is our first practical illustration that pervades this book: achieving speedups that enable the solution of problems that could not otherwise be solved is one of the prime reasons to study algorithm performance and design...
Experienced programmers sometimes choose shellsort because it has acceptable running time even for moderately large arrays; it requires a small amount of code; and it uses no extra space...if you need a solution to a sorting problem, and are working in a situation where a system sort may not be available (for example, code destined for hardware or an embedded system), you can safely use shellsort, then determine sometime later whether it will be worthwhile to replace it with a more sophisticated method.
Below is sort code in Java with a simple client example as described above.
Shellsort:
public class Shell {
public static void sort(int[] a) {
int i, j = 0;
int h = 1;
int temp = 0;
int N = a.length;
while(h < N/3) {
h = 3*h + 1;
}
while(h >= 1) {
for(i = h; i < N; i++) {
for(j = i; j >= h && a[j] < a[j-h]; j -= h) {
temp = a[j];
a[j] = a[j-h];
a[j-h] = temp;
}
}
h = h/3;
}
} //end sort
public static void main(String[] args) {
int[] a = {7,8,12,18,32,6,17,21,13,9,5,8,25,20,16,12,3};
sort(a);
if(isSorted(a)) {
System.out.println("sort succeeded.");
}
else {
System.out.println("sort failed.");
}
}
public static boolean isSorted(int[] a) {
for(int i = 1; i < a.length; i++) {
if(a[i] < a[i-1]) {
return false;
}
}
return true;
}
}