java - big difference in time between two Implementation of quick Sort -
i have 2 implementation of quick sort first 1 uses median of (fist ,middle , last ) pivot , second uses middle element pivot first implementation :
public class quickmedian { public void sort(int array[]) // pre: array full, elements non-null integers // post: array sorted in ascending order { quicksort(array, 0, array.length - 1); // quicksort elements in array } public void quicksort(int array[], int start, int end) { int = start; // index of left-to-right scan int k = end; // index of right-to-left scan if (end - start >= 1) // check there @ least 2 elements sort { if (array[start+(end-start)/2]>array[end]){ swap(array,start+(end-start)/2, end); } if (array[start]>array[end]){ swap(array,start, end); } if (array[start+(end-start)/2]>array[start]){ swap(array, start+(end-start)/2, start); } int pivot = array[start]; // set pivot first element in partition while (k > i) // while scan indices left , right have not met, { while (array[i] <= pivot && <= end && k > i) // left, first i++; // element greater pivot while (array[k] > pivot && k >= start && k >= i) // right, first k--; // element not greater pivot if (k > i) // if left seekindex still smaller swap(array, i, k); // right index, swap corresponding elements } swap(array, start, k); // after indices have crossed, swap last element in // left partition pivot quicksort(array, start, k - 1); // quicksort left partition quicksort(array, k + 1, end); // quicksort right partition } else // if there 1 element in partition, not sorting { return; // array sorted, exit } } public void swap(int array[], int index1, int index2) // pre: array full , index1, index2 < array.length // post: values @ indices 1 , 2 have been swapped { int temp = array[index1]; // store first value in temp array[index1] = array[index2]; // copy value of second first array[index2] = temp; // copy value of temp second } } the second implementation :
public class quicksort { private int array[]; private int length; public void sort(int[] inputarr) { if (inputarr == null || inputarr.length == 0) { return; } this.array = inputarr; length = inputarr.length; quicksorter(0, length - 1); } private void quicksorter(int lowerindex, int higherindex) { int = lowerindex; int j = higherindex; // calculate pivot number, taking pivot middle index number int pivot = array[lowerindex+(higherindex-lowerindex)/2]; // divide 2 arrays while (i <= j) { /** * in each iteration, identify number left side * greater pivot value, , identify number * right side less pivot value. once search * done, exchange both numbers. */ while (array[i] < pivot) { i++; } while (array[j] > pivot) { j--; } if (i <= j) { exchangenumbers(i, j); //move index next position on both sides i++; j--; } } // call quicksort() method recursively if (lowerindex < j) quicksorter(lowerindex, j); if (i < higherindex) quicksorter(i, higherindex); } private void exchangenumbers(int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } } to obtain median need steps on each recursion may increase time a little bit (if array totally random) .
i testing these 2 classes on array of size n=10,000,000 randomly generated , have done test many times first implementation takes around 30 seconds , second takes around 4 seconds not caused overhead median of 3 numbers .
there must wrong first implementation, ?
here testing code :
public static void main(string[] args) { file number = new file ("f.txt"); final int size = 10000000; try{ // quicksort s = new quicksort(); quickmedian s = new quickmedian(); writetofile(number, size); int [] arr1 =readfromfile(number, size); long a=system.currenttimemillis(); s.sort(arr1); long b=system.currenttimemillis(); system.out.println("quicksort: "+(double)(b-a)/1000); }catch (exception ex){ex.printstacktrace();} }
Comments
Post a Comment