fork(2) download
  1. import java.util.Arrays;
  2. import java.util.Random;
  3. import java.util.concurrent.*;
  4.  
  5. class Solution {
  6. Random random = new Random(System.currentTimeMillis());
  7.  
  8. void popul(int[] ar) {
  9. for (int i = 0; i < ar.length; i++) {
  10. ar[i] = random.nextInt();
  11. }
  12. }
  13.  
  14. interface ProcessIntArray {
  15. void process(int[] arr);
  16. }
  17.  
  18. public Future<Double> measure(int[] arr, ProcessIntArray processIntArray, ExecutorService es) {
  19. Callable<Double> task = () -> {
  20. long start = System.nanoTime();
  21. processIntArray.process(arr);
  22. long end = System.nanoTime();
  23. return (end - start) / 1000000000.0;
  24. };
  25. return es.submit(task);
  26. }
  27.  
  28.  
  29. public void start() throws ExecutionException, InterruptedException {
  30. ExecutorService executorService = Executors.newFixedThreadPool(8);
  31.  
  32. int size = 1000 * 1000;
  33. int[] quickSortArray = new int[size];
  34. popul(quickSortArray);
  35. int[] bubbleSortArray = Arrays.copyOf(quickSortArray, quickSortArray.length);
  36. int[] mergeSortArray = Arrays.copyOf(quickSortArray, quickSortArray.length);
  37. int[] originalArray = Arrays.copyOf(quickSortArray, quickSortArray.length);
  38. int[] insertionSortArray = Arrays.copyOf(quickSortArray, quickSortArray.length);
  39.  
  40. Future<Double> bubbleSortTime = measure(bubbleSortArray, Solution::bubbleSort, executorService);
  41. Future<Double> insertionSortTime = measure(insertionSortArray, Solution::insertionSort, executorService);
  42. Future<Double> quickSortTime = measure(quickSortArray, Solution::quickSort, executorService);
  43. Future<Double> mergeSortTime = measure(mergeSortArray, Solution::mergeSort, executorService);
  44.  
  45.  
  46. System.out.println();
  47. System.out.println("array size: " + size);
  48. System.out.println("quick sort: " + quickSortTime.get() + "s");
  49. System.out.println("merge sort: " + mergeSortTime.get() + "s");
  50. System.out.println("insertion sort: " + insertionSortTime.get() + "s");
  51. System.out.println("bubble sort: " + bubbleSortTime.get() + "s");
  52. executorService.shutdown();
  53.  
  54. for (int i = 0; i < quickSortArray.length; i++) {
  55. if (quickSortArray[i] != bubbleSortArray[i] || quickSortArray[i] != mergeSortArray[i] || quickSortArray[i] != insertionSortArray[i]) {
  56. throw new RuntimeException(Arrays.toString(originalArray));
  57. }
  58. }
  59. }
  60.  
  61.  
  62. public static void mergeSort(int[] ar) {
  63. if (ar.length < 5) {
  64. bubbleSort(ar);
  65. return;
  66. }
  67. int pivot = ar.length / 2;
  68. int[] ar2 = new int[pivot];
  69. int[] ar3 = new int[ar.length - pivot];
  70. for (int i = 0; i < ar.length; i++) {
  71. if (i < pivot) {
  72. ar2[i] = ar[i];
  73. } else {
  74. ar3[i - pivot] = ar[i];
  75. }
  76. }
  77. mergeSort(ar2);
  78. mergeSort(ar3);
  79. int ar2idx = 0;
  80. int ar3idx = 0;
  81. int arIndexCounter = 0;
  82. while (true) {
  83. int whatToPutInAR = 0;
  84. if (ar2idx != ar2.length && ar3idx != ar3.length) {
  85. if (ar2[ar2idx] < ar3[ar3idx]) {
  86. whatToPutInAR = ar2[ar2idx];
  87. ar2idx++;
  88. } else {
  89. whatToPutInAR = ar3[ar3idx];
  90. ar3idx++;
  91. }
  92. } else if (ar2idx != ar2.length) {
  93. whatToPutInAR = ar2[ar2idx];
  94. ar2idx++;
  95. } else if (ar3idx != ar3.length) {
  96. whatToPutInAR = ar3[ar3idx];
  97. ar3idx++;
  98. } else if (arIndexCounter != ar.length) {
  99. throw new RuntimeException("wtf");
  100. }
  101. if (arIndexCounter == ar.length) return;
  102. ar[arIndexCounter++] = whatToPutInAR;
  103. }
  104. }
  105.  
  106. private static void quickSort(int[] ar) {
  107. quickSort(ar, 0, ar.length);
  108. }
  109.  
  110. static public void quickSort(int[] array, int start, int end) {
  111. boolean changed = false;
  112. if (end == 0) return;
  113. int pivot = array[end - 1];
  114. int partitionCandidate = start;
  115. for (int i = start; i < end; i++) {
  116. if (array[i] < pivot) {
  117. swap(array, partitionCandidate++, i);
  118. changed = true;
  119. } else if (pivot < array[i]) {
  120. swap(array, end - 1, i);
  121. changed = true;
  122. }
  123. }
  124. if (start < partitionCandidate) {
  125. quickSort(array, start, partitionCandidate);
  126. }
  127. if (partitionCandidate < end) {
  128. if (partitionCandidate != start || changed) quickSort(array, partitionCandidate, end);
  129. }
  130. }
  131.  
  132.  
  133. public static void swap(int[] ar, int from, int to) {
  134. int old = ar[from];
  135. ar[from] = ar[to];
  136. ar[to] = old;
  137. }
  138.  
  139. public static void bubbleSort(int[] ar) {
  140. for (int i = 0; i < ar.length; i++) {
  141. for (int j = 0; j < ar.length - 1; j++) {
  142. if (ar[j] > ar[j + 1]) {
  143. swap(ar, j + 1, j);
  144. }
  145. }
  146. }
  147. }
  148.  
  149. private static void insertionSort(int[] ar) {
  150. for (int i = 0; i < ar.length; i++) {
  151. for (int j = i; j >= 1; j--) {
  152. boolean breaker = true;
  153. if (ar[j] < ar[j - 1]) {
  154. breaker = false;
  155. swap(ar, j - 1, j);
  156. }
  157. if (breaker) break;
  158. }
  159. }
  160. }
  161.  
  162. public static void main(String[] args) throws ExecutionException, InterruptedException {
  163. System.out.println(System.getProperty("java.version"));
  164. Solution s = new Solution();
  165. while (true) s.start();
  166. }
  167. }
Time limit exceeded #stdin #stdout 5s 322112KB
stdin
Standard input is empty
stdout
1.8.0_51

array size:     1000000
quick sort:     0.860230758s
merge sort:     1.185182392s