fork(10) download
copy 
  1. import java.io.IOException;
  2. import java.io.PrintWriter;
  3. import java.util.Arrays;
  4. import java.util.Random;
  5.  
  6.  
  7. /**
  8.  * Generator which creates a test where Java 7 dual-pivot quicksort algorithm runs in O(n^2) time.
  9.  * 
  10.  * Number of operations is not the best possible:
  11.  * maximal recursion depth is about n^2 / 5 while best possible result is n^2 / 4.
  12.  * 
  13.  * It's because Java 7 checks if array is nearly sorted.
  14.  * If it is, a strange algorithm with something called 'runs' is used.
  15.  * In our case it is not, but in process of this checking Java 7 swaps some elements.
  16.  * I didn't figure out how to maintain these swaps yet. Feel free to improve it!
  17.  * 
  18.  * @author Alexey Dergunov
  19.  * @since  1.7
  20.  */
  21. public class Main implements Runnable {
  22.  
  23.     private final Random rnd = new Random(239);
  24.  
  25.     private final int INSERTION_SORT_THRESHOLD = 47;
  26. //    private final int MAX_RUN_LENGTH = 33;
  27. //    private final int QUICKSORT_THRESHOLD = 286;
  28. //    private final int MAX_RUN_COUNT = 67;
  29.  
  30.     private int MIN_VALUE;
  31.     private int MAX_VALUE;
  32.     private final int NO_VALUE = -1;
  33.  
  34.     private void hackedSort(int[] a, int[] p, int left, int right, boolean leftmost) {
  35.         int length = right - left + 1;
  36.  
  37.         // Use insertion sort on tiny arrays
  38.         if (length < INSERTION_SORT_THRESHOLD) {
  39.             for (int i = right; i >= left; i--) {
  40.                 if (a[i] == NO_VALUE) a[i] = MIN_VALUE++;
  41.             }
  42.             randomShuffle(a, left, right); // why not?
  43.  
  44.             if (leftmost) {
  45.                 /*
  46.                  * Traditional (without sentinel) insertion sort,
  47.                  * optimized for server VM, is used in case of
  48.                  * the leftmost part.
  49.                  */
  50.                 for (int i = left, j = i; i < right; j = ++i) {
  51.                     int ai = a[i + 1];
  52.                     int pi = p[i + 1];
  53.                     while (ai < a[j]) {
  54.                         a[j + 1] = a[j];
  55.                         p[j + 1] = p[j];
  56.                         if (j-- == left) {
  57.                             break;
  58.                         }
  59.                     }
  60.                     a[j + 1] = ai;
  61.                     p[j + 1] = pi;
  62.                 }
  63.             } else {
  64.                 /*
  65.                  * Skip the longest ascending sequence.
  66.                  */
  67.                 do {
  68.                     if (left >= right) {
  69.                         return;
  70.                     }
  71.                 } while (a[++left] >= a[left - 1]);
  72.  
  73.                 /*
  74.                  * Every element from adjoining part plays the role
  75.                  * of sentinel, therefore this allows us to avoid the
  76.                  * left range check on each iteration. Moreover, we use
  77.                  * the more optimized algorithm, so called pair insertion
  78.                  * sort, which is faster (in the context of Quicksort)
  79.                  * than traditional implementation of insertion sort.
  80.                  */
  81.                 for (int k = left; ++left <= right; k = ++left) {
  82.                     int a1 = a[k], a2 = a[left];
  83.                     int p1 = p[k], p2 = p[left];
  84.  
  85.                     if (a1 < a2) {
  86.                         a2 = a1; a1 = a[left];
  87.                         p2 = p1; p1 = p[left];
  88.                     }
  89.                     while (a1 < a[--k]) {
  90.                         a[k + 2] = a[k];
  91.                         p[k + 2] = p[k];
  92.                     }
  93.                     ++k;
  94.                     a[k + 1] = a1;
  95.                     p[k + 1] = p1;
  96.  
  97.                     while (a2 < a[--k]) {
  98.                         a[k + 1] = a[k];
  99.                         p[k + 1] = p[k];
  100.                     }
  101.                     a[k + 1] = a2;
  102.                     p[k + 1] = p2;
  103.                 }
  104.                 int last = a[right];
  105.                 int plast = p[right];
  106.  
  107.                 while (last < a[--right]) {
  108.                     a[right + 1] = a[right];
  109.                     p[right + 1] = p[right];
  110.                 }
  111.                 a[right + 1] = last;
  112.                 p[right + 1] = plast;
  113.             }
  114.             return;
  115.         }
  116.  
  117.         // Inexpensive approximation of length / 7
  118.         int seventh = (length >> 3) + (length >> 6) + 1;
  119.  
  120.         /*
  121.          * Sort five evenly spaced elements around (and including) the
  122.          * center element in the range. These elements will be used for
  123.          * pivot selection as described below. The choice for spacing
  124.          * these elements was empirically determined to work well on
  125.          * a wide variety of inputs.
  126.          */
  127.         int e3 = (left + right) >>> 1; // The midpoint
  128.         int e2 = e3 - seventh;
  129.         int e1 = e2 - seventh;
  130.         int e4 = e3 + seventh;
  131.         int e5 = e4 + seventh;
  132.  
  133.         if (a[e5] == NO_VALUE) a[e5] = MIN_VALUE++;
  134.         if (a[e4] == NO_VALUE) a[e4] = MIN_VALUE++;
  135.  
  136.         if (a[e1] == NO_VALUE) a[e1] = MAX_VALUE--;
  137.         if (a[e2] == NO_VALUE) a[e2] = MAX_VALUE--;
  138.  
  139.         // Sort these elements using insertion sort
  140.         if (less(a[e2], a[e1])) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t;
  141.                                   int s = p[e2]; p[e2] = p[e1]; p[e1] = s; }
  142.  
  143.         if (less(a[e3], a[e2])) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
  144.                                   int s = p[e3]; p[e3] = p[e2]; p[e2] = s;
  145.             if (less(t, a[e1])) { a[e2] = a[e1]; a[e1] = t;
  146.                                   p[e2] = p[e1]; p[e1] = s; }
  147.         }
  148.         if (less(a[e4], a[e3])) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
  149.                                   int s = p[e4]; p[e4] = p[e3]; p[e3] = s;
  150.             if (less(t, a[e2])) { a[e3] = a[e2]; a[e2] = t;
  151.                                   p[e3] = p[e2]; p[e2] = s;
  152.                 if (less(t, a[e1])) { a[e2] = a[e1]; a[e1] = t;
  153.                                       p[e2] = p[e1]; p[e1] = s; }
  154.             }
  155.         }
  156.         if (less(a[e5], a[e4])) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
  157.                                   int s = p[e5]; p[e5] = p[e4]; p[e4] = s;
  158.             if (less(t, a[e3])) { a[e4] = a[e3]; a[e3] = t;
  159.                                   p[e4] = p[e3]; p[e3] = s;
  160.                 if (less(t, a[e2])) { a[e3] = a[e2]; a[e2] = t;
  161.                                       p[e3] = p[e2]; p[e2] = s;
  162.                     if (less(t, a[e1])) { a[e2] = a[e1]; a[e1] = t;
  163.                                           p[e2] = p[e1]; p[e1] = s; }
  164.                 }
  165.             }
  166.         }
  167.  
  168.         // Pointers
  169.         int less  = left;  // The index of the first element of center part
  170.         int great = right; // The index before the first element of right part
  171.  
  172.         if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
  173.             /*
  174.              * Use the second and fourth of the five sorted elements as pivots.
  175.              * These values are inexpensive approximations of the first and
  176.              * second terciles of the array. Note that pivot1 <= pivot2.
  177.              */
  178.             int pivot1 = a[e2];
  179.             int pivot2 = a[e4];
  180.             int ppivot1 = p[e2];
  181.             int ppivot2 = p[e4];
  182.  
  183.             /*
  184.              * The first and the last elements to be sorted are moved to the
  185.              * locations formerly occupied by the pivots. When partitioning
  186.              * is complete, the pivots are swapped back into their final
  187.              * positions, and excluded from subsequent sorting.
  188.              */
  189.             a[e2] = a[left];
  190.             a[e4] = a[right];
  191.             p[e2] = p[left];
  192.             p[e4] = p[right];
  193.  
  194.             /*
  195.              * Skip elements, which are less or greater than pivot values.
  196.              */
  197.             //while (a[++less] < pivot1);
  198.             //while (a[--great] > pivot2);
  199.             while (less(a[++less], pivot1));
  200.             while (greater(a[--great], pivot2));
  201.  
  202.             /*
  203.              * Partitioning:
  204.              *
  205.              *   left part           center part                   right part
  206.              * +--------------------------------------------------------------+
  207.              * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
  208.              * +--------------------------------------------------------------+
  209.              *               ^                          ^       ^
  210.              *               |                          |       |
  211.              *              less                        k     great
  212.              *
  213.              * Invariants:
  214.              *
  215.              *              all in (left, less)   < pivot1
  216.              *    pivot1 <= all in [less, k)     <= pivot2
  217.              *              all in (great, right) > pivot2
  218.              *
  219.              * Pointer k is the first index of ?-part.
  220.              */
  221.             outer:
  222.             for (int k = less - 1; ++k <= great; ) {
  223.                 int ak = a[k];
  224.                 int pk = p[k];
  225.                 //if (ak < pivot1) { // Move a[k] to left part
  226.                 if (less(ak, pivot1)) { // Move a[k] to left part
  227.                     a[k] = a[less];
  228.                     p[k] = p[less];
  229.                     /*
  230.                      * Here and below we use "a[i] = b; i++;" instead
  231.                      * of "a[i++] = b;" due to performance issue.
  232.                      */
  233.                     a[less] = ak;
  234.                     p[less] = pk;
  235.                     ++less;
  236.                 //} else if (ak > pivot2) { // Move a[k] to right part
  237.                 } else if (greater(ak, pivot2)) { // Move a[k] to right part
  238.                     //while (a[great] > pivot2) {
  239.                     while (greater(a[great], pivot2)) {
  240.                         if (great-- == k) {
  241.                             break outer;
  242.                         }
  243.                     }
  244.                     //if (a[great] < pivot1) { // a[great] <= pivot2
  245.                     if (less(a[great], pivot1)) { // a[great] <= pivot2
  246.                         a[k] = a[less];
  247.                         p[k] = p[less];
  248.                         a[less] = a[great];
  249.                         p[less] = p[great];
  250.                         ++less;
  251.                     } else { // pivot1 <= a[great] <= pivot2
  252.                         a[k] = a[great];
  253.                         p[k] = p[great];
  254.                     }
  255.                     /*
  256.                      * Here and below we use "a[i] = b; i--;" instead
  257.                      * of "a[i--] = b;" due to performance issue.
  258.                      */
  259.                     a[great] = ak;
  260.                     p[great] = pk;
  261.                     --great;
  262.                 }
  263.             }
  264.  
  265.             // Swap pivots into their final positions
  266.             a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
  267.             a[right] = a[great + 1]; a[great + 1] = pivot2;
  268.             p[left]  = p[less  - 1]; p[less  - 1] = ppivot1;
  269.             p[right] = p[great + 1]; p[great + 1] = ppivot2;
  270.  
  271.  
  272.             // Sort left and right parts recursively, excluding known pivots
  273.             hackedSort(a, p, left, less - 2, leftmost);
  274.             hackedSort(a, p, great + 2, right, false);
  275.  
  276.             /*
  277.              * If center part is too large (comprises > 4/7 of the array),
  278.              * swap internal pivot values to ends.
  279.              */
  280.             if (less < e1 && e5 < great) {
  281.                 /*
  282.                  * Skip elements, which are equal to pivot values.
  283.                  */
  284.                 while (a[less] == pivot1) {
  285.                     throw new RuntimeException("We should not enter here!");
  286. //                    ++less;
  287.                 }
  288.  
  289.                 while (a[great] == pivot2) {
  290.                     throw new RuntimeException("We should not enter here!");
  291. //                    --great;
  292.                 }
  293.  
  294.                 /*
  295.                  * Partitioning:
  296.                  *
  297.                  *   left part         center part                  right part
  298.                  * +----------------------------------------------------------+
  299.                  * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
  300.                  * +----------------------------------------------------------+
  301.                  *              ^                        ^       ^
  302.                  *              |                        |       |
  303.                  *             less                      k     great
  304.                  *
  305.                  * Invariants:
  306.                  *
  307.                  *              all in (*,  less) == pivot1
  308.                  *     pivot1 < all in [less,  k)  < pivot2
  309.                  *              all in (great, *) == pivot2
  310.                  *
  311.                  * Pointer k is the first index of ?-part.
  312.                  */
  313.                 outer:
  314.                 for (int k = less - 1; ++k <= great; ) {
  315.                     int ak = a[k];
  316.                     int pk = p[k];
  317.                     if (ak == pivot1) { // Move a[k] to left part
  318.                         a[k] = a[less];
  319.                         p[k] = p[less];
  320.                         a[less] = ak;
  321.                         p[less] = pk;
  322.                         ++less;
  323.                     } else if (ak == pivot2) { // Move a[k] to right part
  324.                         while (a[great] == pivot2) {
  325.                             if (great-- == k) {
  326.                                 break outer;
  327.                             }
  328.                         }
  329.                         if (a[great] == pivot1) { // a[great] < pivot2
  330.                             a[k] = a[less];
  331.                             p[k] = p[less];
  332.                             /*
  333.                              * Even though a[great] equals to pivot1, the
  334.                              * assignment a[less] = pivot1 may be incorrect,
  335.                              * if a[great] and pivot1 are floating-point zeros
  336.                              * of different signs. Therefore in float and
  337.                              * double sorting methods we have to use more
  338.                              * accurate assignment a[less] = a[great].
  339.                              */
  340.                             a[less] = pivot1;
  341.                             p[less] = ppivot1;
  342.                             ++less;
  343.                         } else { // pivot1 < a[great] < pivot2
  344.                             a[k] = a[great];
  345.                             p[k] = p[great];
  346.                         }
  347.                         a[great] = ak;
  348.                         p[great] = pk;
  349.                         --great;
  350.                     }
  351.                 }
  352.             }
  353.  
  354.             // Sort center part recursively
  355.             hackedSort(a, p, less, great, false);
  356.  
  357.         } else { // Partitioning with one pivot
  358.             throw new RuntimeException("We should not enter here!");            
  359. //            /*
  360. //             * Use the third of the five sorted elements as pivot.
  361. //             * This value is inexpensive approximation of the median.
  362. //             */
  363. //            int pivot = a[e3];
  364. //            int ppivot = p[e3];
  365. //
  366. //            /*
  367. //             * Partitioning degenerates to the traditional 3-way
  368. //             * (or "Dutch National Flag") schema:
  369. //             *
  370. //             *   left part    center part              right part
  371. //             * +-------------------------------------------------+
  372. //             * |  < pivot  |   == pivot   |     ?    |  > pivot  |
  373. //             * +-------------------------------------------------+
  374. //             *              ^              ^        ^
  375. //             *              |              |        |
  376. //             *             less            k      great
  377. //             *
  378. //             * Invariants:
  379. //             *
  380. //             *   all in (left, less)   < pivot
  381. //             *   all in [less, k)     == pivot
  382. //             *   all in (great, right) > pivot
  383. //             *
  384. //             * Pointer k is the first index of ?-part.
  385. //             */
  386. //            for (int k = less; k <= great; ++k) {
  387. //                if (a[k] == pivot) {
  388. //                    continue;
  389. //                }
  390. //                int ak = a[k];
  391. //                int pk = p[k];
  392. //                if (less(ak, pivot)) { // Move a[k] to left part
  393. //                    a[k] = a[less];
  394. //                    p[k] = p[less];
  395. //                    a[less] = ak;
  396. //                    p[less] = pk;
  397. //                    ++less;
  398. //                } else { // a[k] > pivot - Move a[k] to right part
  399. //                    while (greater(a[great], pivot)) {
  400. //                        --great;
  401. //                    }
  402. //                    if (less(a[great], pivot)) { // a[great] <= pivot
  403. //                        a[k] = a[less];
  404. //                        p[k] = p[less];
  405. //                        a[less] = a[great];
  406. //                        p[less] = p[great];
  407. //                        ++less;
  408. //                    } else { // a[great] == pivot
  409. //                        /*
  410. //                         * Even though a[great] equals to pivot, the
  411. //                         * assignment a[k] = pivot may be incorrect,
  412. //                         * if a[great] and pivot are floating-point
  413. //                         * zeros of different signs. Therefore in float
  414. //                         * and double sorting methods we have to use
  415. //                         * more accurate assignment a[k] = a[great].
  416. //                         */
  417. //                        a[k] = pivot;
  418. //                        p[k] = ppivot;
  419. //                    }
  420. //                    a[great] = ak;
  421. //                    p[great] = pk;
  422. //                    --great;
  423. //                }
  424. //            }
  425. //
  426. //            /*
  427. //             * Sort left and right parts recursively.
  428. //             * All elements from center part are equal
  429. //             * and, therefore, already sorted.
  430. //             */
  431. //            hackedSort(a, p, left, less - 1, leftmost, depth + 1);
  432. //            hackedSort(a, p, great + 1, right, false, depth + 1);
  433.         }
  434.     }
  435.  
  436.     private void randomShuffle(int[] a, int left, int right) {
  437.         for (int i = left; i <= right; i++) {
  438.             int j = left + rnd.nextInt(i - left + 1);
  439.             swap(a, i, j);
  440.         }
  441.     }
  442.  
  443.     private void swap(int[] a, int i, int j) {
  444.         int t = a[i];
  445.         a[i] = a[j];
  446.         a[j] = t;
  447.     }
  448.  
  449.     private boolean less(int a, int b) {
  450.         if (a != NO_VALUE && b != NO_VALUE) {
  451.             return a < b;
  452.         }
  453.         if (a == NO_VALUE) {
  454.             return b > MAX_VALUE;
  455.         }
  456.         if (b == NO_VALUE) {
  457.             return a < MIN_VALUE;
  458.         }
  459.         throw new RuntimeException("We should not enter here!");
  460.     }
  461.  
  462.     private boolean greater(int a, int b) {
  463.         if (a != NO_VALUE && b != NO_VALUE) {
  464.             return a > b;
  465.         }
  466.         if (a == NO_VALUE) {
  467.             return b < MIN_VALUE;
  468.         }
  469.         if (b == NO_VALUE) {
  470.             return a > MAX_VALUE;
  471.         }
  472.         throw new RuntimeException("We should not enter here!");
  473.     }
  474.  
  475.     public void run() {
  476.         int n = 60000;
  477.  
  478.         int[] a = new int[n];
  479.         int[] p = new int[n];
  480.  
  481.         for (int i = 0; i < n; i++) {
  482.             a[i] = NO_VALUE;
  483.             p[i] = i;
  484.         }
  485.         MIN_VALUE = 1;
  486.         MAX_VALUE = n;
  487.  
  488.         long t1, t2;
  489.  
  490.         t1 = System.currentTimeMillis();
  491.         hackedSort(a, p, 0, n-1, true);
  492.         t2 = System.currentTimeMillis();
  493.         System.out.println("Generation time = " + (t2 - t1) + " ms.");
  494.  
  495.         checkValues(a, 1, n);
  496.         checkValues(p, 0, n-1);
  497.  
  498.         applyPermutation(a, p);
  499.  
  500.         /*
  501.         try {
  502.             printArray(a, new PrintWriter("output.txt"));
  503.         } catch (IOException e) {
  504.             throw new RuntimeException(e);
  505.         }
  506.         */
  507.  
  508.         t1 = System.currentTimeMillis();
  509.         Arrays.sort(a.clone());
  510.         t2 = System.currentTimeMillis();
  511.         System.out.println("Sorting time = " + (t2 - t1) + " ms.");
  512.     }
  513.  
  514.     private void applyPermutation(int[] a, int[] pos) {
  515.         int n = a.length;
  516.         int[] tmp = new int[n];
  517.         for (int i = 0; i < n; i++) {
  518.             tmp[pos[i]] = a[i];
  519.         }
  520.         for (int i = 0; i < n; i++) {
  521.             a[i] = tmp[i];
  522.             pos[i] = i;
  523.         }
  524.     }
  525.  
  526.     private void checkValues(int[] a, int min, int max) {
  527.         boolean[] b = new boolean[max - min + 1];
  528.         for (int x : a) {
  529.             if (b[x - min]) {
  530.                 throw new RuntimeException();
  531.             }
  532.             b[x - min] = true;
  533.         }
  534.     }
  535.  
  536.     private void printArray(int[] a, PrintWriter pw) {
  537.         int n = a.length;
  538.         pw.println(n);
  539.         for (int i = 0; i < n; i++) {
  540.             pw.print(a[i]);
  541.             if (i == n-1) pw.println(); else pw.print(' ');
  542.         }
  543.         pw.close();
  544.     }
  545.  
  546.     public static void main(String[] args) {
  547.         new Thread(null, new Main(), "", 128*1024*1024).start();
  548.     }
  549.  
  550. }
  551.  
Success #stdin #stdout 14.42s 380928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Generation time = 10884 ms.
Sorting time = 3460 ms.
https://ideone.com/IokO6m
language:
Java (12.0.1)
created:
10 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!