Shell Sort in JAVA

Introduction

 
In today's article, we discuss Shell Sort in Java.
 

Shell Sort

 
Shell Sort, named after its inventor, Donald. L. Shell (1959), relies upon the fact that an Insertion Sort does very well if the array is nearly sorted. The Shell Sort, sometimes called the "diminishing increment sort" improves on the Insertion Sort by splitting the original list into a number of smaller sublists, each of which is sorted using an Insertion Sort. Another way of saying this is that an Insertion Sort does well if it does not have to move each item "too far". The idea is to repeatedly do the Insertion Sort on all elements at fixed, decreasing distances apart: hk, hk-1, ..., h1= 1. The choice of increments turns out to be crucial. It turns out that a good choice of increments are these.
 
Code Description
 
The unique way is the choice of the key for the Shell Sort. Instead of splitting the list into sublists of contiguous items, the Shell Sort uses an increment "i", sometimes called the gap, to create a sublist by choosing all items that are "i" items apart.
 
h1= 1, h2= 3, h3= 7, ..., hk= 2k–1
 
These increments are called the Hibbard increments. The original increments suggested by the algorithm's inventor were simple powers of 2. They are able to use the hk increment, you need an array of size at least hk+1.
 
In this list there are nine items. If we use an increment of three then there are three sublists generated, each of which can be sorted by an Insertion Sort. After completing these sorts, we get the list shown in Fig-3. Although this list is not completely sorted, something very interesting has happened. By sorting the sub lists, we have moved the items closer to where they actually belong.
 
Shell Sort in JAVA
 
A Shell Sort with increments of three
 
Shell Sort in JAVA
 
A Shell Sort after sorting each sublist
 
The following figure shows a final Insertion Sort using an increment of one; in other words, a standard Insertion Sort. Note that by performing the earlier sublist sorts, we have now reduced the total number of shifting operations necessary to put the list in its final order. For this case, we only need four more shifts to complete the process.
 
Shell Sort in JAVA
 
A Final Insertion Sort with Increment of 1
 

Advantages of Shell Sort

  1. It is fast in nature
  2. It performs more operations and has higher cache miss ratio than quicksort
  3. It is easy to understand
  4. It is easy to implement
  5. Shell Sort is now rarely used in serious applications
Example
  1. public class ShellSortEx  
  2. {      
  3.     public static void main(String a[])  
  4.     {  
  5.         //Numbers which are to be sorted  
  6.         int n[] = {88,33,77,55,99,22,11,66,44};  
  7.         //Displays the numbers before sorting  
  8.         System.out.print("Before sorting, numbers are ");  
  9.         for(int i = 0; i < n.length; i++)  
  10.           {  
  11.             System.out.print(n[i]+" ");  
  12.           }  
  13.         System.out.println();  
  14.         //Sorting in ascending order using Shell Sort  
  15.         initializemergeSort(n);;  
  16.         //Displaying the numbers after sorting  
  17.         System.out.print("After sorting, numbers are ");  
  18.         for(int i = 0; i < n.length; i++)  
  19.           {  
  20.             System.out.print(n[i]+" ");  
  21.           }  
  22.     }  
  23.     public static void initializemergeSort(int n[])   
  24.     {  
  25.         int i1,i,j,increment,temp, no_of_elem=n.length;  
  26.         /* Shell Sort Program */  
  27.         for (increment=no_of_elem/2;increment>0;increment/=2)  
  28.         {  
  29.             for(i=increment;i<no_of_elem;i++)  
  30.             {  
  31.                 temp=n[i];  
  32.                 for(j=i;j>=increment;j-=increment)   
  33.                 {  
  34.                     if(temp<n[j-increment])  
  35.                     {  
  36.                         n[j]=n[j-increment];  
  37.                     }  
  38.                     else   
  39.                     {  
  40.                         break;  
  41.                     }  
  42.                 }  
  43.                 n[j] = temp;  
  44.             }  
  45.         }  
  46.     }  
  47. }  
Output
 
Shell Sort in JAVA