ShellSorter.java.html

  1  import java.util.ArrayList;
  2  
  3  /**
  4     The sort method of this class sorts an array, using the Shell
  5     sort algorithm.
  6  */
  7  public class ShellSorter
  8  {
  9     /**
 10        Sorts an array, using selection sort.
 11        @param a the array to sort
 12     */
 13     public static void sort(int[] a)
 14     {  
 15        // Generate the sequence values
 16        ArrayList<Integer> columns = new ArrayList<Integer>();
 17        int c = 1;
 18        while (c < a.length) 
 19        { 
 20           columns.add(c);
 21           c = 3 * c + 1;          
 22        }
 23  
 24        // For each column count, sort all columns
 25        for (int s = columns.size() - 1; s >= 0; s--)
 26        {
 27           c = columns.get(s);
 28           for (int k = 0; k < c; k++)
 29           {
 30              insertionSort(a, k, c);
 31           }         
 32        }
 33     }
 34  
 35     /**
 36        Sorts a column, using insertion sort.
 37        @param a the array to sort
 38        @param k the index of the first element in the column
 39        @param c the gap between elements in the column
 40     */
 41     public static void insertionSort(int[] a, int k, int c)
 42     {
 43        for (int i = k + c; i < a.length; i = i + c)
 44        {
 45           int next = a[i];
 46           // Move all larger elements up
 47           int j = i;
 48           while (j >= c && a[j - c] > next)
 49           {
 50              a[j] = a[j - c];
 51              j = j - c;
 52           }
 53           // Insert the element
 54           a[j] = next;
 55        }
 56     }
 57  }