Shell Sort
17 July 2009, 06:09 PM
The basic idea in shellsort is to exchange every hth element in the array. Now this can be confusing so we'll talk more on this. h determine how far apart element exchange can happen, say for example take h as 13, the first element (index-0) is exchanged with the 14th element (index-13) if necessary (of course). The second element with the 15th element, and so on. Now if we take h as 1, it is exactly the same as a regular insertion sort.
Shellsort works by starting with big enough (but not larger than the array size) h as to allow elligible element exchanges that are far apart. Once a sort is complete with a particular h, the array can be said as h-sorted. The next step is to reduce h by a certain sequence, and again performing another complete h-sort. Once h is 1 and h-sorted, the array is completely sorted. Notice that the last sequence for h is 1 so the last sort is always an insertion sort, except by this time the array is already well-formed and easier to sort.
recommended h sequence:
..., 1093, 364, 121, 40, 13, 4, 1.
Applet: ShellSort demo applet. Click to reset with new random elements.
Take a look at above applet and see how small elements near the right-end are transfered quickly to the left side. Generally shellsort first rearrange the array so the smaller elements appear on the left side and larger elements on the right side, and finally does a normal insertion sort with a breeze.
/** * Shellsort data. sorting is in-place. * @param data Array to sort. */
public void sort(int[] data) {// find the largest h
// sequence used is ..., 1093, 364, 121, 40, 13, 4, 1.
int h = 1, v, j ; do { h = h * 3 + 1 ; } while (h < data.length) ; do { h = h / 3 ; for (int i = h; i < data.length; i++) { v = data[i] ; j = i ; while ((j >= h) && (data[j-h] > v)) { data[j] = data[j-h] ; j -= h ; } data[j] = v ; } } while (h > 1) ; }
Shellsort is an excellent sort and by far surpasses its other elementary alternatives. It is an algorithm of choice for its implementation simplicity and acceptable runtime for moderately large number of elements. This is the kind of algorithm you'll want to use to get something working fast and at the same time does not suck. Well yes, until you are ready for the extra work dealing with complex non-elementary sort for about double the speed (except for very large array). Until then avoid bubble sort, selection sort, or insertion sort and use shellsort instead :)
Last edited on 5 September 2009
Comments
Post a comment~