Shell Sort

Main

import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.Locale;
import java.util.Random;

public class Foothill {
   public static final int ARRAY_SIZE = 1000000;

   public static void main(String[] args) {
      Integer[] arrayOfInts1 = new Integer[ARRAY_SIZE];
      Integer[] arrayOfInts2 = new Integer[ARRAY_SIZE];

      // ... other gap arrays ...
      int[] gapArray = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,
            4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576 };
      int[] sedgewickArray = new int[30]; // to be computed using formulas
      int[] sedgewick2Array = new int[30];
      int[] hibbardArray = new int[30];
      int[] prattArray = new int[30];
      int[] gonnetArray = fillGonnetArray(ARRAY_SIZE);
      int[] myAlgo = new int[30];

      // fill gap arrays
      fillSedgewick(sedgewickArray);
      fillHibbard(hibbardArray);
      fillPratt(prattArray);
      fillSedgewick2(sedgewick2Array);
      myOwnArray(myAlgo, ARRAY_SIZE);
      // fill distinct arrays with identical random values so we can compare
      // gaps
      
      Random rand = new Random();
      for (int i = 0; i < ARRAY_SIZE; i++) {
         // find integer values from 1->ARRAY_SIZE
         arrayOfInts2[i] = arrayOfInts1[i] = rand.nextInt(ARRAY_SIZE);
      }
      long startTime, stopTime;

      NumberFormat tidy = NumberFormat.getInstance(Locale.US);
      tidy.setMaximumFractionDigits(4);

      startTime = System.nanoTime();
      shellSortX(arrayOfInts1, gapArray); // time this
      stopTime = System.nanoTime();

      System.out.println("Shell's gap N/(2^k) [O(N^2)], Elapsed time: "
            + tidy.format((stopTime - startTime) / 1e9) + "seconds.");
      System.out.println("Array size: " + ARRAY_SIZE);

      resetArray(arrayOfInts1, arrayOfInts2);

      startTime = System.nanoTime();
      shellSortX(arrayOfInts1, gapArray); // time this
      stopTime = System.nanoTime();

      System.out.println("Normal gap 2^k [O(N^2)], Elapsed time: "
            + tidy.format((stopTime - startTime) / 1e9) + "seconds.");
      System.out.println("Array size: " + ARRAY_SIZE);

      resetArray(arrayOfInts1, arrayOfInts2);

      startTime = System.nanoTime();
      shellSortX(arrayOfInts1, sedgewickArray); // time this
      stopTime = System.nanoTime();

      System.out.println("Sedgewick gap 4^k + 3*2^(k-1) + 1 [O(N^4/3)] Elapsed time: "
            + tidy.format((stopTime - startTime) / 1e9) + "seconds.");
      System.out.println("Array size: " + ARRAY_SIZE);
      
      resetArray(arrayOfInts1, arrayOfInts2);

      startTime = System.nanoTime();
      shellSortX(arrayOfInts1, sedgewick2Array); // time this
      stopTime = System.nanoTime();

      System.out.println("Sedgewick gap #2 9*(4^(k-1) - 2^(k-1)) + 1 [O(N^4/3)] Elapsed time: "
            + tidy.format((stopTime - startTime) / 1e9) + "seconds.");
      System.out.println("Array size: " + ARRAY_SIZE);

      resetArray(arrayOfInts1, arrayOfInts2);

      startTime = System.nanoTime();
      shellSortX(arrayOfInts1, hibbardArray); // time this
      stopTime = System.nanoTime();

      System.out.println("Hibbard gap 2^k - 1 [O(N^(3/2))] Elapsed time: "
            + tidy.format((stopTime - startTime) / 1e9) + "seconds.");
      System.out.println("Array size: " + ARRAY_SIZE);

      resetArray(arrayOfInts1, arrayOfInts2);

      startTime = System.nanoTime();
      shellSortX(arrayOfInts1, prattArray); // time this
      stopTime = System.nanoTime();

      for(int i : prattArray){
         System.out.println(i);
      }
      
      System.out.println("Pratt gap 2^q3^p [O(NlogN)]Elapsed time: "
            + tidy.format((stopTime - startTime) / 1e9) + "seconds.");
      System.out.println("Array size: " + ARRAY_SIZE);
      
      resetArray(arrayOfInts1, arrayOfInts2);

      startTime = System.nanoTime();
      shellSortX(arrayOfInts1, gonnetArray); // time this
      stopTime = System.nanoTime();
      
      System.out
            .println("Gonnet & Baeza-Yates gap floor(Hk = (5Hk-1/11)) where H0 = SIZE_ARRAY, [O(Unknown)]Elapsed time: "
            + tidy.format((stopTime - startTime) / 1e9) + "seconds.");
      System.out.println("Array size: " + ARRAY_SIZE);
      /*
      resetArray(arrayOfInts1, arrayOfInts2);

      startTime = System.nanoTime();
      shellSortX(arrayOfInts1, myAlgo); // time this
      stopTime = System.nanoTime();
      
      System.out
            .println("Ray Zhang gap [O(Unknown)]Elapsed time: "
            + tidy.format((stopTime - startTime) / 1e9) + "seconds.");
      System.out.println("Array size: " + ARRAY_SIZE);*/

   }

   /**
    * Default shell sort with size = arraySize/2
    * 
    * @param a
    *           , array to be passed in.
    */
   public static <E extends Comparable<? super E>> void shellSortX(E[] a) {
      int ONE = 1;

      int k, pos, arraySize;
      E tmp;

      arraySize = a.length;
      for (ONE = arraySize / 2; ONE > 0; ONE /= 2)
         for (pos = ONE; pos < arraySize; pos++) {
            tmp = a[pos];
            for (k = pos; k >= ONE && tmp.compareTo(a[k - ONE]) < 0; k -= ONE)
               a[k] = a[k - ONE];
            a[k] = tmp;
         }
   }

   public static <E extends Comparable<? super E>> void shellSortX(E[] a,
         int[] gaps) {
      int k, pos, arraySize;
      E tmp;

      arraySize = a.length;
      for (int i = gaps.length-1; i >= 0; i--) {
         for (pos = gaps[i]; pos < arraySize; pos++) {
            tmp = a[pos];
            for (k = pos; k >= gaps[i] && tmp.compareTo(a[k - gaps[i]]) < 0; k -= gaps[i]) {
               a[k] = a[k - gaps[i]];
            }
            a[k] = tmp;
         }
      }
   }

   public static void fillSedgewick(int[] gap) {
      // prefix with 1
      gap[0] = 1;
      for (int i = 1; i < gap.length; i++) {
         gap[i] = (int) (Math.pow(4, i) + 3 * (Math.pow(2, i - 1)) + 1);
      }
   }

   public static void fillHibbard(int[] gap) {
      for (int i = 0; i < gap.length; i++) {
         gap[i] = (int) (Math.pow(2, (i + 1)) - 1);
      }
   }

   public static void fillPratt(int[] gap) {
      gap[0] = 1;
      int m2 = 0, m3 = 0;
      for(int i = 1; i < gap.length; i ++){
         int p2 = gap[m2] * 2;
         int p3 = gap[m3] * 3;
         if( p2 < p3 ){
            gap[i] = p2;
            m2++;
         }
         else if( p2 > p3 ){
            gap[i] = p3;
            m3++;
         }
         else{
            gap[i] = p2;
            m2++;
            m3++;
         //otherwise duplication
         }
      }
   }
   public static int[] fillGonnetArray(int size){
      ArrayList<Integer> gArr = new ArrayList<Integer>();
      int i = size * 5 /11 ;
      //will always arrive at 2, then go to 0
      while(i > 1){
         gArr.add(0, i);
         i = i * 5 / 11;
      }
      gArr.add(0, 1);
      Integer[] temp = gArr.toArray(new Integer[gArr.size()]);
      int[] t = new int[temp.length];
      for(int s = 0; s < temp.length; s++)
         t[s] = temp[s];
      return t;
   }
   
   public static void fillSedgewick2(int[] gap){
      for(int k = 0; k < gap.length/2; k++){
         //prevent overflow
         int firstTerm =  9 * (int) ((Math.pow(4, k)) - (int) (Math.pow(2, k))) + 1;
         int secondTerm = (int) (Math.pow(4, k+2)) - 6 * (int)(Math.pow(2, k+1)) + 1;
         if(firstTerm > 0)
            gap[k*2] = firstTerm;
         else
            gap[k*2] = Integer.MAX_VALUE;
         if(secondTerm > 0)
            gap[k*2+1] = secondTerm;
         else
            gap[k*2+1] = Integer.MAX_VALUE;
      }
   }
   
   public static void myOwnArray(int[] gap, int size){
      for(int i = gap.length-1; i >= 0; i--){
         gap[i] = size*15/7;
         size = (int)(((double)size / 11) * 9);
      }
      while(gap[0] > 1){
         for(int i = gap.length-1; i >= 0; i--){
            gap[i] = gap[i]*5/11;
         }
      }
   }

   /**
    * Utility method: assumes both are of same size
    */
   public static <E> void resetArray(E[] a, E[] b) {
      for (int i = 0; i < a.length; i++) {
         a[i] = b[i];
      }
   }
}

Output.txt

Shell's gap N/(2^k) [O(N^2)], Elapsed time: 22.0737seconds.
Array size: 1000000
Normal gap 2^k [O(N^2)], Elapsed time: 19.7306seconds.
Array size: 1000000
Sedgewick gap 4^k + 3*2^(k-1) + 1 [O(N^4/3)] Elapsed time: 2.2773seconds.
Array size: 1000000
Sedgewick gap #2 9*(4^(k-1) - 2^(k-1)) + 1 [O(N^4/3)] Elapsed time: 2.3961seconds.
Array size: 1000000
Hibbard gap 2^k - 1 [O(N^(3/2))] Elapsed time: 3.5459seconds.
Array size: 1000000
Pratt gap 2^q3^p [O(NlogN)]Elapsed time: 43.468seconds.
Array size: 1000000
Gonnet & Baeza-Yates gap floor(Hk = (5Hk-1/11)) where H0 = SIZE_ARRAY, [O(Unknown)]Elapsed time: 2.6709seconds.
Array size: 1000000