Monday, March 26, 2012

Shell Sort - Let the shelling begin

So, many of us already know about insertion sort which is a nice sorting algorithm for sorting but lacks in performance, with complexity of O(n2), but gives a good performance when it comes to almost sorted list.

Using this property of fast processing in case of almost sorted list, Shell sort can achieve much better results then insertion sort. Shell sort does this by doing a "incremental sort" of the array. By that i mean it first divides the array into parts and sorts the elements relative to each other.

E.g. Array = 5 2 4 1 6 3 7

Lets take a interval of 4 and consider every 4rd element in this array

so we will compare 5, 1 and 7 and will sort these element relative to each other.

new Array = 1 2 4 5 6 3 7

In the next iteration we will consider a smaller number, finally we will reach to a point where we will have a interval of 1 and will be a simple insertion sort but by that time must of the element would be in there positions or very near to there final positions making this a fast iteration.

So we start with a big "Shell" and imagine these are the only elements in the array and sort then move on to making them smaller and smaller till we have a shell size of 1. As you may have noticed key is the division rule or the series(called a "Gap Sequence"or "Interval Sequence") we will use to decide on the shell sizes. Remember we need to have a series which ends with 1 so that we can run the insertion sort in the end. One of these series is provided by Kunth,

h = 3*h + 1

now in word of Kunfu Panda "enough talk, let's code"


 
 /**
 * This method will sort the array 
 * using Kunth's formula to calculate 
 * the bucket.
 */
public void shellSort() {
 int inner;
 int outer;
 int h = 1;
 /**
  * Calculate the bucket size to the max
  * then we move down till we reach around 1
  */
 while(h <= (nElemt/3)){
  h = h*3 + 1;
 }
 while(h > 0){
  for(outer = h; outer < nElemt; outer++){
   int temp = array[outer];
   inner = outer;
   while(inner > h-1 && 
                                    array[inner - h] >= temp){
    array[inner] = array[inner - h];
    inner -= h;
   }
   array[inner] = temp;
  }
  h = (h-1) / 3; //get the value of bucket back
 }
}

References :
Data Structures and Algorithms in Java by Robert Lafore

No comments: