fork download
copy 
  1. import java.util.concurrent.TimeUnit;
  2.  
  3. public class Main {
  4.     static long last = 42;
  5.     static final long a = 25214903917L; // Multiplier
  6.     static final long c = 11; // Increment
  7.     static final long m = 1L << 48; // Modulus
  8.  
  9.     static int nextInt(int bound) {
  10.         last = (a * last + c) % m;
  11.         return (int) (last % bound);
  12.     }
  13.  
  14.     // Quick Sort
  15.     static void quickSort(int[] arr, int low, int high) {
  16.         if (low < high) {
  17.             // pi is partitioning index, arr[pi] is now at right place
  18.             int pi = partition(arr, low, high);
  19.  
  20.             // Recursively sort elements before partition and after partition
  21.             quickSort(arr, low, pi - 1);
  22.             quickSort(arr, pi + 1, high);
  23.         }
  24.     }
  25.  
  26.     // A utility function to swap two elements
  27.     static void swap(int[] arr, int i, int j) {
  28.         int temp = arr[i];
  29.         arr[i] = arr[j];
  30.         arr[j] = temp;
  31.     }
  32.  
  33.     /* This function takes last element as pivot, places the pivot element at its correct position in sorted array,
  34.     and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */
  35.     static int partition(int[] arr, int low, int high) {
  36.         int pivot = arr[high];
  37.         int i = (low - 1); // index of smaller element
  38.         for (int j = low; j < high; j++) {
  39.             // If current element is smaller than the pivot
  40.             if (arr[j] < pivot) {
  41.                 i++;
  42.                 // swap arr[i] and arr[j]
  43.                 swap(arr, i, j);
  44.             }
  45.         }
  46.         // swap arr[i+1] and arr[high] (or pivot)
  47.         swap(arr, i + 1, high);
  48.         return i + 1;
  49.     }
  50.  
  51.     public static void main(String[] args) {
  52.         final int N = 100;
  53.         int[] arr = new int[N];
  54.  
  55.         final int M = 50;
  56.         long[] sortingTimes = new long[M];
  57.  
  58.         long start = System.nanoTime();
  59.  
  60.         // Save initial value of last
  61.         long initialLast = last;
  62.  
  63.         for (int i = 1; i <= M; i++) {
  64.             // Restore initial value of last
  65.             last = initialLast;
  66.  
  67.             for (int j = 0; j < N; j++) {
  68.                 arr[j] = nextInt(1007);
  69.             }
  70.  
  71.             long sortStart = System.nanoTime();
  72.  
  73.             // Sorting algorithm
  74.             quickSort(arr, 0, arr.length - 1);
  75.  
  76.             long sortStop = System.nanoTime();
  77.             long sortDuration = sortStop - sortStart;
  78.  
  79.             // Add value of time in array in nanoseconds
  80.             sortingTimes[i - 1] = sortDuration;
  81.         }
  82.  
  83.         // Average time in nanoseconds
  84.         long averageTime = 0;
  85.         for (int i = 0; i < M; i++) {
  86.             averageTime += sortingTimes[i];
  87.         }
  88.         System.out.println("Average Time: " + (double) averageTime / M + " nanoseconds");
  89.     }
  90. }
Success #stdin #stdout 0.16s 58348KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Average Time: 343411.56 nanoseconds
https://ideone.com/973FxA
language:
Java (HotSpot 12)
created:
34 days 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!