ASP.NET - Shell Sort

 Shell Sort

The shell sort is a "diminishing increment sort", better known as a "comb sort" to the unwashed programming masses. The algorithm makes multiple passes through the list, and each time sorts a number of equally sized sets using the Insertion Sort. The size of the set to be sorted gets larger with each pass through the list, until the set consists of the entire list. (Note that as the size of the set increases, the number of sets to be sorted decreases.)

The items contained in each set are not contiguous - rather, if there are i sets then a set is composed of every i-th element. For example, if there are 3 sets then the first set would contain the elements located at positions 1, 4, 7 and so on. The second set would contain the elements located at positions 2, 5, 8, and so on; while the third set would contain the items located at positions 3, 6, 9, and so on.

The size of the sets used for each iteration has a major impact on the efficiency of the sort.

The shell sort is more than 5 times faster than the bubble sort and a little over twice as fast as the Insertion Sort, its closest competitor.

The shell sort is still significantly slower than the Merge Sort, Heap Sort, and Quick Sorts, but its relatively simple algorithm makes it a good choice for sorting lists of less than 5000 items unless speed is hyper-critical. It's also an excellent choice for repetitive sorting of smaller lists.

Shell Sort Routine Code

// array of integers to hold values
private int[] a = new int[100];
 
// number of elements in array
private int x;
 
// Shell Sort Algorithm
public void sortArray()
{
  int i, j, increment, temp;
 
  increment = 3;
 
  while( increment > 0 )
  {
    for( i=0; i < x; i++ )
    {
      j = i;
      temp = a[i];
 
      while( (j >= increment) && (a[j-increment] > temp) )
      {
        a[j] = a[j - increment];
        j = j - increment;
      }
 
      a[j] = temp;
    }
 
    if( increment/2 != 0 )
    {
      increment = increment/2;
    }
    else if( increment == 1 )
    {
      increment = 0;
    }
    else
    {
      increment = 1;
    }
  }
}