Advertisement
Guest User

Unfinished Shell Sort

a guest
Feb 17th, 2016
24
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.25 KB | None | 0 0
  1. public class ShellSort {
  2.    
  3.     private static int CopyCount;//create static integer CopyCount
  4.     private static int CompareCount;//create static integer CompareCount
  5.    
  6.     public static Results shellSort(int [] items, int gapSequenceFormuler){
  7.        
  8.         CopyCount=0; //count number of times elements in an array are copied
  9.         CompareCount=0; //count number of times elements in an array are compared to each-other
  10.        
  11.         //generate sequence of gap sizes to use in insertion sort
  12.        
  13.         int k=1; //k is >=1
  14.         int gap = 1; //initialize gap size
  15.         Stack<Integer> gapsizes = new Stack<Integer>(); //create stack to store gap-sizes
  16.        
  17.         if(gapSequenceFormuler == 0) //if gapsequenceformula = 0, use this formula
  18.             do{
  19.                 gap = ((int) Math.pow(3, k)-1)/2; //use a gap increment sequence generated by the formula (3^k -1)/2
  20.                 k++;                                //increment k
  21.                 if(gap<items.length/3)              //store gap-sizes in stack, except for last one, which exceeds array size / 3
  22.                     gapsizes.push(gap);
  23.             }while(gap<items.length/3); //gaps should not exceed array size / 3
  24.        
  25.         else if(gapSequenceFormuler == 1)    //if gapsequenceformula = 1, use this formula
  26.             gapsizes.push(1);               //push gap size 1 to gap sequence since this loop doesnt generate it for some reason
  27.             do{
  28.                 gap=(int) Math.pow(4, k) + (3*(int) Math.pow(2, k-1)) +1; //use a gap increment sequence generated by the formula 4^k +3*2^(k-1) +1
  29.                 k++;                                //increment k
  30.                 if(gap<items.length/3)              //store gap-sizes in stack, except for last one, which exceeds array size / 3
  31.                     gapsizes.push(gap);
  32.             }while(gap<items.length/3);         //gaps should not exceed array size / 3
  33.            
  34.            
  35.         System.out.println("array size is " + items.length); //print out array size to console
  36.         System.out.println("gap sequence is " + gapsizes);  //print gap sequence to console
  37.        
  38.         /*move gapsequence from stack to array so that numbers are in reverse order*/
  39.         /*int [] gaps = new int[gapsizes.size()]; //new array has size equal to number of elements in stack
  40.         int i = 0; //initialize variable i
  41.         while(gapsizes.empty() == false){//while the stack has elements in it
  42.               gaps[i] = gapsizes.pop(); //new array[i] = element popped from stack
  43.               i++;}//increment i*/
  44.        
  45.         //return null;
  46.        
  47.         while(gapsizes.empty() == false){
  48.             int i = gapsizes.pop();
  49.             for(int g = 0; g < i; g++){
  50.                 InsertionSort(items, i, g);
  51.     }}
  52.        
  53.         return new Results(CopyCount, CompareCount);    //return Results Object that holds CompareCount and CopyCount values
  54.     }
  55.  
  56.     private static void InsertionSort (int [] a, int gapsize, int offset){ //insertion sort
  57.        
  58.         //System.out.println(Arrays.toString(gaps));//print out gap array to console
  59.        
  60.             for (int i = gapsize + offset; i < a.length; i = i + gapsize){
  61.                 int temp = a[i];
  62.                 CopyCount++;    //increments CopyCount
  63.                 int j = i;
  64.            
  65.                 while (j >= gapsize/*0*/ && temp < a[j-gapsize/*1*/]){
  66.                     CompareCount++; //increments CompareCount
  67.                     a[j] = a[j - gapsize];//a[j+1] = a[j]; //
  68.                     CopyCount++;    //increments CopyCount
  69.                     j--;
  70.                 }
  71.                 if(j>= gapsize/*>0*/)
  72.                     CompareCount++; //increments CompareCount if j only fulfills first condition and breaks while loop
  73.                
  74.                 a[j/*+1*/] = temp;  
  75.                 CopyCount++;    //increments CopyCount
  76.             }  
  77.             System.out.println(Arrays.toString(a));
  78.     }
  79.    
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement