fork(2) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1.8.0_51

array size:     1000000
quick sort:     0.860230758s
merge sort:     1.185182392s
https://ideone.com/1E8C51
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!