Advertisement
Guest User

Untitled

a guest
Sep 23rd, 2019
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.87 KB | None | 0 0
  1. package yourid;
  2.  
  3. import java.lang.reflect.Array;
  4. import java.util.*;
  5.  
  6. public class QuickSort {
  7. //cutoffs, you should run experiments to find good values
  8. public static int a = 5;
  9. public static int b =1000000000;
  10. public static int c = 100;
  11. public static Random random = new Random();
  12. public static void sort(int[] array){
  13. sort(array,0,array.length-1);
  14. }
  15.  
  16. //You need to implement this
  17. private static void shuffle(int[] a){
  18. for(int i = 0; i<a.length;i++){
  19. int randPos = random.nextInt(a.length);
  20. int temp = a[i];
  21. a[i]=a[randPos];
  22. a[randPos]=temp;
  23. }
  24. }
  25.  
  26. //You need to implement this
  27. private static int partitionByMedianOf3(int[] array, int lo, int hi){
  28. int middle = (hi-lo)/2;
  29. int pivot = median3(array,lo,middle,hi);
  30. int temp = array[pivot];
  31. array[pivot] = array[lo];
  32. array[lo] = temp;
  33. return partition(array,lo,hi);
  34. }
  35.  
  36. //You need to implement this
  37. private static int partitionByMedianOf9(int[] array, int lo, int hi){
  38. int middle = (hi-lo)/2;
  39. int m1 = median3(array,lo,middle,hi);
  40. int m2 = median3(array,lo+1,middle-1,hi-1);
  41. int m3 = median3(array,lo+2,middle+1,hi-2);
  42. int pivot = median3(array,m1,m2,m3);
  43. int temp = array[pivot];
  44. array[pivot] = array[lo];
  45. array[lo] = temp;
  46. return partition(array,lo,hi);
  47. }
  48.  
  49. private static int median3(int[] array,int i,int j, int k){
  50. int temp[] = new int[]{array[i],array[j],array[k]};
  51. insertionSort(temp,0,2);
  52. if(temp[1]==array[i])return i;
  53. else if (temp[1]==array[j])return j;
  54. else return k;
  55. }
  56. //You need to implement this
  57. public static void insertionSort(int[] array, int lo, int hi){
  58. int compares = 0;
  59. for(int i = lo; i<=hi;i++){
  60. for(int j = compares;j>0;j--){
  61. if(array[j]<array[j-1]){
  62. int temp = array[j];
  63. array[j]=array[j-1];
  64. array[j-1]=temp;
  65. }else {
  66. break;
  67. }
  68.  
  69. }
  70. compares++;
  71. }
  72.  
  73. }
  74.  
  75. //partion by the first element
  76. private static int partition(int[] array, int lo, int hi){
  77. int pivot = array[lo], i = lo, j = hi+1;
  78. while (true){
  79. while (array[++i] < pivot) if (i == hi) break;
  80. while (array[--j] > pivot) if (j == lo) break;
  81. if (i >= j) break;
  82. int tmp = array[i];
  83. array[i] = array[j];
  84. array[j] = tmp;
  85. }
  86. array[lo] = array[j];
  87. array[j] = pivot;
  88. return j;
  89. }
  90.  
  91. //You should modify this to use the various cutoffs
  92. private static void sort(int[] array, int lo, int hi){
  93. int j;
  94. int N = hi-lo;
  95. if(N<a){
  96. insertionSort(array, lo, hi);
  97. return;
  98. }
  99.  
  100. if (hi <= lo) return;
  101. j = partition(array, lo, hi);
  102. /*
  103. if(N<b){
  104. j = partition(array,lo,hi);
  105. }else if(N<c){
  106. j = partitionByMedianOf3(array, lo, hi);
  107. }
  108. else {
  109. j = partitionByMedianOf9(array,lo,hi);
  110. }*/
  111.  
  112. //recursively sort the left and right subarray
  113. sort(array, lo, j-1);
  114. sort(array, j+1, hi);
  115. }
  116.  
  117.  
  118.  
  119. //You can use this for testing, we will not grade it
  120. public static void main(String args[]) throws Exception{
  121. b = 1000000000;
  122. figureA(5);
  123. /* int[] ints = GenerateArray(1000);
  124. sort(ints);
  125. if(!test(ints)){
  126. System.err.println("not sorted");
  127. }
  128. int[] ints = GenerateArray(1000000);
  129. shuffle(ints);
  130. Utilities.startTimer();
  131. sort(ints);
  132. System.out.println(Utilities.checkTimer());
  133.  
  134. for (int i:ints){
  135. System.out.println(i);
  136. }
  137. System.out.println(test(ints));*/
  138. }
  139. public static int[] GenerateArray(int size){
  140. int[] temp = new int[size];
  141. for(int i=0;i<size;i++){
  142. temp[i] = random.nextInt(2000000000);
  143. }
  144. return temp;
  145. }
  146.  
  147. public static boolean test(int[] array){
  148. int k = array.length;
  149. for(int i = 1; i<k;i++){
  150. if(array[i-1]>array[i]){
  151. return false;
  152. }
  153. }
  154. return true;
  155. }
  156.  
  157. public static void figureA(int k){
  158. b = 20;
  159. a = k;
  160. Utilities.startTimer();
  161. for(int i = 0;i<100000;i++){
  162. int[] ints = GenerateArray(1000);
  163. sort(ints);
  164. if(!test(ints)){
  165. System.err.println("not sorted");
  166. }
  167. }
  168. System.out.println("avgTime(a="+a+"): "+Utilities.checkTimer()/10.0);
  169. }
  170.  
  171. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement