Shell sort Java example

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 i开发者_如何学运维t's too difficult.

---

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.

---

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();
      }
    }

---

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;
    }
}
}

---

Here is a visualization of shell sort for a python implementation:

def exch(a,i,j):
  t = a[i]
  a[i] = a[j]
  a[j] = t

def shellsort(string):
  print string
  a = list(string)
  N = len(a)
  h = 1
  i = 0
  j = 0
  k = 0
  #determine starting stride length
  while ( h < N/3 ):
    h = 3*h + 1
  print "STRIDE LENGTH: " + str(h)
  while (h >=1):
    i = h
    while i < N:
      j = i
      k = j - h
      while j >= h and a[j] < a[j-h]:
        k = j - h
        exch(a,j,k)
        j -= h
      i += 1
    h = h/3
    print "STRIDE LENGTH: " + str(h)
  print ''.join(a)·


if __name__ == '__main__':
    shellsort("astringtosortwithshellsort")

---

Here's an example:

public static void shellsort( Comparable [ ] a )
    {
        for( int gap = a.length / 2; gap > 0;
                     gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) )
            for( int i = gap; i < a.length; i++ )
            {
                Comparable tmp = a[ i ];
                int j = i;

                for( ; j >= gap && tmp.compareTo( a[ j - gap ] ) < 0; j -= gap )
                    a[ j ] = a[ j - gap ];
                a[ j ] = tmp;
            }
    }

---

I find the easiest way to understand shell sort is to break it down into segments:

private static void shellsort() {
    int[] theArray = {44,5,33,22,765,43,53,12,57,97};

    //first section gets the Knuth's interval sequence (very efficient)
    int h=1;
    while(h<= theArray.length/3){
        h = 3*h + 1;   //h is equal to highest sequence of h<=length/3 (1,4,13,40...)
    }

    //next section
    while(h>0){    //for array of length 10, h=4

       //similar to insertion sort below
       for(int i=0; i<theArray.length; i++){ 

            int temp = theArray[i]; 
            int j;              

            for(j=i; j>h-1 && theArray[j-h] >= temp; j=j-h){
                a[j] = a[j-h];                  
            }
            a[j] = temp;
        }
        h = (h-1)/3; 
    }
}

Output: 5, 12, 22, 33, 43, 44, 53, 57, 97, 765

---

Classic primitive type implementation:

package math;

import java.util.Arrays;

public class Sorter{

    public static void main(String []args){
        int[] a = {9,8,7,6,5,4,3,2,1};//plz use sophisticated random number generator
        System.out.println( Arrays.toString(a) );
        System.out.println( Arrays.toString(shellSort(a)) );
    }

    //Performs a shell sort on an array of ints.
    public static int[] shellSort(int[] array){
        int h = 1;
        while (h < array.length) h = 3*h + 1;
        while (h > 0){
            h = h/3;
            for (int k = 0; k < h; k++){
                for (int i = h+k; i < array.length; i+=h){
                    int key = array[i];
                    int j = i-h;
                    while (j>=0 && array[j] > key){
                        array[j+h] = array[j];
                        j-=h;
                    }
                    array[j+h] = key;
                    //-> invariant: array[0,h,2*h..j] is sorted
                }
            }
            //->invariant: each h-sub-array is sorted
        }
        return array;
    };
}

P.S.: Check this link for other sorting algorithms (they are in c++, though, easily portable to java).

---

package sort_tester;

public class ShellSorter extends Sorter {

private final int[] gapArray = {1750,701,301,132,57,23,10,4,1};

@Override
public void makeSort (boolean trace) {

    int size = list.length;
    int i,j, temp;

    for ( int gap : gapArray ) {

        i = gap;

        while ( i < size ) {
            temp = list[i];
            j = i-gap;
            while ( j >= 0 && list[j] > temp ) {
                list[j + gap] = list[j];
                j -= gap;
            }
            list[j + gap] = temp;
            i ++;
        }
    }
}
}

list - is int[]; GapArray taken from arcticle of Marcin Ciura http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf

---

Here is a video link: https://youtu.be/SCBf7aqKQEY The guy has made a good video of shell sort!!

And a simple code:

int sort(int arr[])
{
    int n = arr.length;
    int gap = n/2;
    int i,j;

    while(gap>0)
     {  for (i=0,j=i+gap; j<n; i++,++j)
        {     
           if(arr[i]>arr[j])                   //swap
              { int temp = arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
              } 

        }
        gap=gap/2;
     }
    return 0;
}

---

Use this

 public void shellSort(Integer[] arr) {

    int interval = arr.length / 2;

    while (interval != 0) {

        for (int i = 0; i < interval; i++) {

            for (int p = i + interval; p < arr.length; p += interval) {

                int key = arr[p];
                int j = p - interval;
                while (j >= 0) {

                    if (key < arr[j]) {
                        arr[j + interval] = arr[j];
                    } else 
                        break;
                    j -= interval;
                } 

                arr[j + interval] = key;

            } 
        }

        interval /= 2;

    }
}

---

Snippet with 3k+1 gap.

public void shellSort(Comparable arr[], int size, int h, int x) {
        while (h >= 1) {
            for (int i = 0; i <= size - h; i++) {
                for (int j = i; j < size-h && (arr[j].compareTo(arr[j+h]) > 0); j += h)
                    swap(arr, j, j+h);      
            }
            h = 3*(--x) + 1;
        }
    }