Shell Sort Program and Complexity (Big-O)


Shellsort is an in-place comparison sort, also known as Shell sort or Shell’s method. It’s mainly variation of insertion sort or bubble sort . There was one drawback with insertion sort, we move elements only one position ahead but when an elements are too far then lots of movements are involved. To reduce these movements Shell sort come with idea of allow exchange of far items.

Shell Sort Steps

  • Pick some far location h and make sorted array for values index[h…n-1] by insertion sort.
  • Reduce the value of h until it becomes 1.
  • Repeat the steps 1 and 2
  • Finally you will get sorted items list.

Points to Remember

  • Data structure: Array
  • Worst-case performance: O(n2) (worst known worst case gap sequence) O(n log2n) (best known worst case gap sequence)
  • Best-case performance: O(n log n) (most gap sequences) O(n log2n)  (best known worst case gap sequence)
  • Average performance: depends on gap sequence
  • Worst-case space complexity : О(n) total, O(1) auxiliary

Sell Sort Java Program

public class ShellSort {
 public static void main(String[] args)
 {
		int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
        System.out.println("Before Shell Sorting :");
        printArray(items);

        //Perform shell sort
        shellsort(items);

        System.out.println("After Shell Sorting :");
        printArray(items);
 }
 static void shellsort(int items[])
 {
     int n = items.length; 

     // Start with a big gap, then reduce the gap until 1
     for (int gap = n/2; gap > 0; gap /= 2)
     {
    	 //perform insertion sort for these gap size
    	 //The first gap elements a[0..gap-1] are already
    	 //in gapped order keep adding one more element
    	 //until the entire array is gap sorted 

         for (int i = gap; i = gap && items[j - gap] > temp; j -= gap)
            	 items[j] = items[j - gap]; 

             // put temp in its correct  location
             items[j] = temp;
         }
     } 

 } 

 static void printArray(int items[])
	{
     for (int item:items)
     {
         System.out.print(item + " ");
     }
     System.out.println();
	}
}

Output

 


Before Shell Sorting :
2 6 3 8 4 1 5 0 
After Shell Sorting :
0 1 2 3 4 5 6 8 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s