Tech-Algorithm.com

Shellsort is actually a simple extension for insertion sort. The primary difference is its capability of exchanging elements that are far apart, making it considerably faster for elements to get to where it should be. For example if the smallest element happens to be at the end of an array, with insertion sort it will require a full array steps to put this element at the beginning of the array. However with shellsort, this element can jump further instead of just one step a time and reach the proper destination in less exchanges.

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 :)