Shell sort Java example

Question

Can anyone give me example about shell sort? I'm a new person in here who must learn about shell sort, but first I must find a Java shell sort example. I found one example in Google but it's too difficult.

Answer 1

Here, this code is very simple :

/**
   * Shellsort, using Shell’s (poor) increments.
   * @param a an array of Comparable items.
   */
  public static <T extends Comparable<? super T>>
  void shellsort( T [ ] a )
  {
    int j;
    for( int gap = a.length / 2; gap > 0; gap /= 2 )
    {
      for( int i = gap; i < a.length; i++ )
      {
         T tmp = a[ i ];
         for( j = i; j >= gap && tmp.compareTo( a[ j - gap ] ) < 0; j -= gap )
         {
           a[ j ] = a[ j - gap ];
         }
         a[ j ] = tmp;
      }
    }
  }

I stole it from a book called Data Structures and Algorithm Analysis in Java. It is very good book easy to understand. I advise you to read it.

Answer 2

May be, this java code will help you.

 public class ShellSort {
       private long[] data;

      private int len;

      public ShellSort(int max) {
        data = new long[max];
        len = 0;
      }

      public void insert(long value){
        data[len] = value; 
        len++;
      }

      public void display() {
        System.out.print("Data:");
        for (int j = 0; j < len; j++)
          System.out.print(data[j] + " ");
        System.out.println("");
      }

      public void shellSort() {
        int inner, outer;
        long temp;
        //find initial value of h
        int h = 1;
        while (h <= len / 3)
          h = h * 3 + 1; // (1, 4, 13, 40, 121, ...)

        while (h > 0) // decreasing h, until h=1
        {
          // h-sort the file
          for (outer = h; outer < len; outer++) {
            temp = data[outer];
            inner = outer;
            // one subpass (eg 0, 4, 8)
            while (inner > h - 1 && data[inner - h] >= temp) {
              data[inner] = data[inner - h];
              inner -= h;
            }
            data[inner] = temp;
          }
          h = (h - 1) / 3; // decrease h
        }
      }

      public static void main(String[] args) {
        int maxSize = 10;
        ShellSort arr = new ShellSort(maxSize);

        for (int j = 0; j < maxSize; j++) {
          long n = (int) (java.lang.Math.random() * 99);
          arr.insert(n);
        }
        arr.display();
        arr.shellSort();
        arr.display();
      }
    }

Answer 3

Shell sort improves insertion sort by comparing elements separated by a gap of several positions.

This lets an element take "bigger steps" toward its expected position. Multiple passes over the data are taken with smaller and smaller gap sizes. The last step of Shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be almost sorted.

This code might help you in understanding the logic better.

package Sorts;
public class ShellSort extends Sorter{

@Override
public <T extends Comparable<? super T>> void sort(T[] a) {
    int h = 1;
    while((h*3+1) < a.length)
        h = 3*h+1;
    while(h > 0){
        for(int i = h-1; i < a.length; i++){
            T s = a[i];
            int j = i;
            for(j = i; (j>=h) && (a[j-h].compareTo(s) > 0); j-=h)
                a[j] = a[j-h];
            a[j] = s;
        }
        h /= 3;
    }
}
}