Shell Sort (Advanced sorting )

Shell Sort is an improvement of Insertion Sort. Insertion sort is working efficiently for almost sorted arrays. But if an element is in far away from where it should be, It is need to do lot of movements.  What shell sort does is first make the array almost sorted and then do one by one sort with insertion sort.
So what we do is divide array into sub arrays and sort each sub array individually.Each sub array consists with elements in fixed intervals. First we decide the size of interval. Then divide array into sub arrays. After that, each sub array is sorted.
Consider the following array of 280 elements.
1. We decide interval size as 121.
2.Divide the array in to sub arrays. Each sub array consists with elements in 121 interval.

figure 01

figure 01 shows three sub arrays (0 121 242),(1 122 243) and (2 123 244). You can see each sub array consists of elements in fixed intervals.

Then these sub arrays are sorted individually. The sub arrays are   (0 121 242),(1 122 243), (2 123 244) .................(157 278),(158 279). Above figure shows only 3 sub arrays. 

Then the first sub array (shown in color blue)  is sorted as we did in Insertion sort(refer the insertion sort post).

We sorted the first sub array. Then the 2nd sub array is sorted. Then the 3rd one and so on. (figure 02)

figure 02

Now we have sorted all sub arrays of interval 121. 

Then reduce the interval to 40 and again divide sub arrays of interval 40(figure 03).

figure 03

Again each sub array is sort. According to above figure, blue color elements green color elements and red color elements are sort. (figure 04)

figure 04

Then again reduce interval to 13. Divide array into sub arrays of lengths of 13. Sort each array. 

Again Reduce the length to 4 and do the same. Then reduce length to 1. 

Java code for Shell Sort

public class ShellArray {

	int nElemns;
	double[] shellArray;
	int maxSize;
	
	public ShellArray(int size){
		maxSize=size;
		shellArray=new double[maxSize];
		nElemns=0;
	}
	
	public void insert(double d){
		shellArray[nElemns++]=d;
	}
	
	public void shellSort(){
		int h=1;
		while(h<=nElemns/3)
			h=h*3+1;
		
		while(h>0){
			int out,in;
			for( out=h;out<nElemns;out++){
				double temp=shellArray[out];
				in=out;
				while(in>h-1 && temp<shellArray[in-h]){
					shellArray[in]=shellArray[in-h];
					in-=h;
				}
				
				shellArray[in]=temp;
				
			}
			
			h=(h-1)/3;
		}
	}
	
	public void display(){
		for(int i=0;i<nElemns;i++){
			System.out.print(shellArray[i]+" ");
		}
		System.out.println("");
	}

}

Runner class

 public class Runner {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		ShellArray shell=new ShellArray(10);
		shell.insert(13);
		shell.insert(18);
		shell.insert(22);
		shell.insert(15);
		shell.insert(33);
		shell.insert(45);
		shell.insert(8);
		shell.insert(11);
		shell.insert(17);
		shell.insert(3);
		
		shell.display();
		shell.shellSort();
		shell.display();

	}
}

The output

The above figure shows the output. First line shows the unsorted array and the sorted array shown in second line.

Overview

I have described above the first step is to divide the array into sub arrays. To do it we first decide the interval. The following formula calculates the first interval.  

           int h=1;  
           while(h<=nElemns/3)  
                h=h*3+1;

Assume the number of elements of an array is 380. The formula calculates the interval starts from 1 and increases the value according to the formula. till it less than 380/3. 

h  h*3+1

1   4

4   13

13  40

40  121

 121 364

The above table shows the h values and h*3+1 values.364 > 380/3.So 121 is the closest value satisfy the condition. 364 is grater than 380/3.So the while loop stops when h=121. The opening interval is 121 for the array consists with 280
elements.

while(h>0){ //the code h=(h-1)/3; } 

This while loop reduce the interval from starting value (121) to 1. (121, 40, 13, 4, 1)




for( out=h;out<nElemns;out++)
This for loop increase the out value from 121 to 279.

while(in>h-1 && temp<shellArray[in-h]){
shellArray[in]=shellArray[in-h];
in-=h;
}


When first in=121, check it is grater than 120 and move untill found shellArray[in-h]less or equal temp. According to our example compare shellArray[121] with shellArray[0]. If shellArray[0]>shellArray[121], shellArray[0] moved into 121 position. Insert shellArray[121] in 0th position.

We started with 121. Then sort (121, 0),(122, 1),(123, 2),..........(242, 121, 0),(243, 122, 1).....You may wonder why 0 121 and 242 are not sorted. The thing actually happen is 0 and 121 sorted first. Then out increment by one , 1 and 122 are sorted. When out become 242 it compare with 121 and 0. Then 0 121 and 242 are sorted.

Then the while loop reduce h to 40. Then sorted (40, 0),(41,1),(42,2) .............(80,40,0),(81,41,1),(82,42,2)...........(120,80,40,0),(121,81,41,1),(122,82,42,2)........... etc.

Please comment If you need any clarifications :)