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.

     

      A Shell Sort with increments of three

    

      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.

     

      A Final Insertion Sort with Increment of 1

Advantages

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

public class ShellSortEx
  {   
    public static void main(String a[])
      {
        //Numbers which are to be sorted
        int n[] = {88,33,77,55,99,22,11,66,44};
        //Displays the numbers before sorting
        System.out.print("Before sorting, numbers are ");
        for(int i = 0; i < n.length; i++)
          {
            System.out.print(n[i]+" ");
          }
        System.out.println();
        //Sorting in ascending order using Shell Sort
        initializemergeSort(n);;
        //Displaying the numbers after sorting
        System.out.print("After sorting, numbers are ");
        for(int i = 0; i < n.length; i++)
          {
            System.out.print(n[i]+" ");
          }
      }
    public static void initializemergeSort(int n[])
      {
        int i1,i,j,increment,temp, no_of_elem=n.length;
        /* Shell Sort Program */
        for (increment=no_of_elem/2;increment>0;increment/=2)
          {
            for(i=increment;i<no_of_elem;i++)
              {
                temp=n[i];
                for(j=i;j>=increment;j-=increment)
                  {
                    if(temp<n[j-increment])
                      {
                        n[j]=n[j-increment];
                      }
                    else
                      {
                        break;
                      }
                  }
                n[j] = temp;
              }
          }
      }
  }

Output