Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class ShellSort {
- private static int CopyCount;//create static integer CopyCount
- private static int CompareCount;//create static integer CompareCount
- public static Results shellSort(int [] items, int gapSequenceFormuler){
- CopyCount=0; //count number of times elements in an array are copied
- CompareCount=0; //count number of times elements in an array are compared to each-other
- //generate sequence of gap sizes to use in insertion sort
- int k=1; //k is >=1
- int gap = 1; //initialize gap size
- Stack<Integer> gapsizes = new Stack<Integer>(); //create stack to store gap-sizes
- if(gapSequenceFormuler == 0) //if gapsequenceformula = 0, use this formula
- do{
- gap = ((int) Math.pow(3, k)-1)/2; //use a gap increment sequence generated by the formula (3^k -1)/2
- k++; //increment k
- if(gap<items.length/3) //store gap-sizes in stack, except for last one, which exceeds array size / 3
- gapsizes.push(gap);
- }while(gap<items.length/3); //gaps should not exceed array size / 3
- else if(gapSequenceFormuler == 1) //if gapsequenceformula = 1, use this formula
- gapsizes.push(1); //push gap size 1 to gap sequence since this loop doesnt generate it for some reason
- do{
- 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
- k++; //increment k
- if(gap<items.length/3) //store gap-sizes in stack, except for last one, which exceeds array size / 3
- gapsizes.push(gap);
- }while(gap<items.length/3); //gaps should not exceed array size / 3
- System.out.println("array size is " + items.length); //print out array size to console
- System.out.println("gap sequence is " + gapsizes); //print gap sequence to console
- /*move gapsequence from stack to array so that numbers are in reverse order*/
- /*int [] gaps = new int[gapsizes.size()]; //new array has size equal to number of elements in stack
- int i = 0; //initialize variable i
- while(gapsizes.empty() == false){//while the stack has elements in it
- gaps[i] = gapsizes.pop(); //new array[i] = element popped from stack
- i++;}//increment i*/
- //return null;
- while(gapsizes.empty() == false){
- int i = gapsizes.pop();
- for(int g = 0; g < i; g++){
- InsertionSort(items, i, g);
- }}
- return new Results(CopyCount, CompareCount); //return Results Object that holds CompareCount and CopyCount values
- }
- private static void InsertionSort (int [] a, int gapsize, int offset){ //insertion sort
- //System.out.println(Arrays.toString(gaps));//print out gap array to console
- for (int i = gapsize + offset; i < a.length; i = i + gapsize){
- int temp = a[i];
- CopyCount++; //increments CopyCount
- int j = i;
- while (j >= gapsize/*0*/ && temp < a[j-gapsize/*1*/]){
- CompareCount++; //increments CompareCount
- a[j] = a[j - gapsize];//a[j+1] = a[j]; //
- CopyCount++; //increments CopyCount
- j--;
- }
- if(j>= gapsize/*>0*/)
- CompareCount++; //increments CompareCount if j only fulfills first condition and breaks while loop
- a[j/*+1*/] = temp;
- CopyCount++; //increments CopyCount
- }
- System.out.println(Arrays.toString(a));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement