Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Java 7 Quicksort Killer

By: a guest on Jul 5th, 2012  |  syntax: Java  |  size: 12.65 KB  |  views: 437  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class QuicksortKiller implements Runnable {
  5.  
  6.         final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
  7.        
  8.         PrintWriter out;
  9.        
  10.         @Override
  11.         public void run() {
  12.                 try {
  13.                         if (ONLINE_JUDGE) {
  14.                                 out = new PrintWriter(System.out);
  15.                         } else {
  16.                                 out = new PrintWriter("output.txt");
  17.                         }
  18.                         Locale.setDefault(Locale.US);
  19.                         solve();
  20.                         out.close();
  21.                 } catch (Throwable e) {
  22.                         e.printStackTrace(System.err);
  23.                         System.exit(-1);
  24.                 }
  25.         }
  26.        
  27.         public static void main(String[] args) {
  28.                 new Thread(null, new QuicksortKiller(), "", 256 * 1024 * 1024).start();
  29.         }
  30.        
  31. //------------------------------------------------------------------------------
  32.  
  33.         final int INSERTION_SORT_THRESHOLD = 47;
  34.        
  35.         private void hackedSort(int[] a, int left, int right, boolean leftmost) {
  36.         int length = right - left + 1;
  37.  
  38.         // Use insertion sort on tiny arrays
  39.         if (length < INSERTION_SORT_THRESHOLD) {
  40.             if (leftmost) {
  41.                
  42.                 for (int i = left; i <= right; i++) {
  43.                         if (a[i] == Integer.MIN_VALUE) a[i] = maxNum--;
  44.                 }
  45.  
  46.                 /*
  47.                  * Traditional (without sentinel) insertion sort,
  48.                  * optimized for server VM, is used in case of
  49.                  * the leftmost part.
  50.                  */
  51.                 for (int i = left, j = i; i < right; j = ++i) {
  52.                     int ai = a[i + 1];
  53.                     int pi = p[i + 1];
  54.                     while (ai < a[j]) {
  55.                         a[j + 1] = a[j];
  56.                         p[j + 1] = p[j];
  57.                         if (j-- == left) {
  58.                             break;
  59.                         }
  60.                     }
  61.                     a[j + 1] = ai;
  62.                     p[j + 1] = pi;
  63.                 }
  64.             } else {
  65.                
  66.                 for (int i = left+1; i <= right; i++) {
  67.                         if (a[i] == Integer.MIN_VALUE) a[i] = maxNum--;
  68.                 }
  69.                 if (a[left] == Integer.MIN_VALUE) a[left] = maxNum--;
  70.  
  71.                 /*
  72.                  * Skip the longest ascending sequence.
  73.                  */
  74.                 do {
  75.                     if (left >= right) {
  76.                         return;
  77.                     }
  78.                 } while (a[++left] >= a[left - 1]);
  79.  
  80.                 /*
  81.                  * Every element from adjoining part plays the role
  82.                  * of sentinel, therefore this allows us to avoid the
  83.                  * left range check on each iteration. Moreover, we use
  84.                  * the more optimized algorithm, so called pair insertion
  85.                  * sort, which is faster (in the context of Quicksort)
  86.                  * than traditional implementation of insertion sort.
  87.                  */
  88.                 for (int k = left; ++left <= right; k = ++left) {
  89.                     int a1 = a[k], a2 = a[left];
  90.                     int p1 = p[k], p2 = p[left];
  91.  
  92.                     if (a1 < a2) {
  93.                         a2 = a1; a1 = a[left];
  94.                         p2 = p1; p1 = p[left];
  95.                     }
  96.                     while (a1 < a[--k]) {
  97.                         a[k + 2] = a[k];
  98.                         p[k + 2] = p[k];
  99.                     }
  100.                     ++k;
  101.                     a[k + 1] = a1;
  102.                     p[k + 1] = p1;
  103.  
  104.                     while (a2 < a[--k]) {
  105.                         a[k + 1] = a[k];
  106.                         p[k + 1] = p[k];
  107.                     }
  108.                     a[k + 1] = a2;
  109.                     p[k + 1] = p2;
  110.                 }
  111.                 int last = a[right];
  112.                 int plast = p[right];
  113.  
  114.                 while (last < a[--right]) {
  115.                     a[right + 1] = a[right];
  116.                     p[right + 1] = p[right];
  117.                 }
  118.                 a[right + 1] = last;
  119.                 p[right + 1] = plast;
  120.             }
  121.             return;
  122.         }
  123.  
  124.         // Inexpensive approximation of length / 7
  125.         int seventh = (length >> 3) + (length >> 6) + 1;
  126.  
  127.         /*
  128.          * Sort five evenly spaced elements around (and including) the
  129.          * center element in the range. These elements will be used for
  130.          * pivot selection as described below. The choice for spacing
  131.          * these elements was empirically determined to work well on
  132.          * a wide variety of inputs.
  133.          */
  134.         int e3 = (left + right) >>> 1; // The midpoint
  135.         int e2 = e3 - seventh;
  136.         int e1 = e2 - seventh;
  137.         int e4 = e3 + seventh;
  138.         int e5 = e4 + seventh;
  139.        
  140.         if (a[e1] == Integer.MIN_VALUE) a[e1] = maxNum--;
  141.         if (a[e2] == Integer.MIN_VALUE) a[e2] = maxNum--;
  142.         if (a[e3] == Integer.MIN_VALUE) a[e3] = maxNum--;
  143.         if (a[e4] == Integer.MIN_VALUE) a[e4] = maxNum--;
  144.         if (a[e5] == Integer.MIN_VALUE) a[e5] = maxNum--;
  145.  
  146.         // Sort these elements using insertion sort
  147.         if (a[e2] < a[e1]) {
  148.                 int t = a[e2]; a[e2] = a[e1]; a[e1] = t;
  149.                 int pt= p[e2]; p[e2] = p[e1]; p[e1] = pt;
  150.         }
  151.  
  152.         if (a[e3] < a[e2]) {
  153.                 int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
  154.                 int pt= p[e3]; p[e3] = p[e2]; p[e2] = pt;
  155.             if (t < a[e1]) {
  156.                 a[e2] = a[e1]; a[e1] = t;
  157.                 p[e2] = p[e1]; p[e1] = pt;
  158.             }
  159.         }
  160.         if (a[e4] < a[e3]) {
  161.                 int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
  162.                 int pt= p[e4]; p[e4] = p[e3]; p[e3] = pt;
  163.             if (t < a[e2]) {
  164.                 a[e3] = a[e2]; a[e2] = t;
  165.                 p[e3] = p[e2]; p[e2] = pt;
  166.                 if (t < a[e1]) {
  167.                         a[e2] = a[e1]; a[e1] = t;
  168.                         p[e2] = p[e1]; p[e1] = pt;
  169.                 }
  170.             }
  171.         }
  172.         if (a[e5] < a[e4]) {
  173.                 int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
  174.                 int pt= p[e5]; p[e5] = p[e4]; p[e4] = pt;
  175.             if (t < a[e3]) {
  176.                 a[e4] = a[e3]; a[e3] = t;
  177.                 p[e4] = p[e3]; p[e3] = pt;
  178.                 if (t < a[e2]) {
  179.                         a[e3] = a[e2]; a[e2] = t;
  180.                         p[e3] = p[e2]; p[e2] = pt;
  181.                     if (t < a[e1]) {
  182.                         a[e2] = a[e1]; a[e1] = t;
  183.                         p[e2] = p[e1]; p[e1] = pt;
  184.                     }
  185.                 }
  186.             }
  187.         }
  188.  
  189.         // Pointers
  190.         int less  = left;  // The index of the first element of center part
  191.         int great = right; // The index before the first element of right part
  192.  
  193.         if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
  194.             /*
  195.              * Use the second and fourth of the five sorted elements as pivots.
  196.              * These values are inexpensive approximations of the first and
  197.              * second terciles of the array. Note that pivot1 <= pivot2.
  198.              */
  199.             int pivot1 = a[e2]; int ppivot1 = p[e2];
  200.             int pivot2 = a[e4]; int ppivot2 = p[e4];
  201.  
  202.             /*
  203.              * The first and the last elements to be sorted are moved to the
  204.              * locations formerly occupied by the pivots. When partitioning
  205.              * is complete, the pivots are swapped back into their final
  206.              * positions, and excluded from subsequent sorting.
  207.              */
  208.             a[e2] = a[left];  p[e2] = p[left];
  209.             a[e4] = a[right]; p[e4] = p[right];
  210.  
  211.             /*
  212.              * Skip elements, which are less or greater than pivot values.
  213.              */
  214.             while (a[++less] < pivot1);
  215.             while (a[--great] > pivot2);
  216.  
  217.             /*
  218.              * Partitioning:
  219.              *
  220.              *   left part           center part                   right part
  221.              * +--------------------------------------------------------------+
  222.              * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
  223.              * +--------------------------------------------------------------+
  224.              *               ^                          ^       ^
  225.              *               |                          |       |
  226.              *              less                        k     great
  227.              *
  228.              * Invariants:
  229.              *
  230.              *              all in (left, less)   < pivot1
  231.              *    pivot1 <= all in [less, k)     <= pivot2
  232.              *              all in (great, right) > pivot2
  233.              *
  234.              * Pointer k is the first index of ?-part.
  235.              */
  236.             outer:
  237.             for (int k = less - 1; ++k <= great; ) {
  238.                 int ak = a[k];
  239.                 int pk = p[k];
  240.                 if (ak < pivot1) { // Move a[k] to left part
  241.                     a[k] = a[less];
  242.                     p[k] = p[less];
  243.                     /*
  244.                      * Here and below we use "a[i] = b; i++;" instead
  245.                      * of "a[i++] = b;" due to performance issue.
  246.                      */
  247.                     a[less] = ak;
  248.                     p[less] = pk;
  249.                     ++less;
  250.                 } else if (ak > pivot2) { // Move a[k] to right part
  251.                     while (a[great] > pivot2) {
  252.                         if (great-- == k) {
  253.                             break outer;
  254.                         }
  255.                     }
  256.                     if (a[great] < pivot1) { // a[great] <= pivot2
  257.                         a[k] = a[less];
  258.                         p[k] = p[less];
  259.                         a[less] = a[great];
  260.                         p[less] = p[great];
  261.                         ++less;
  262.                     } else { // pivot1 <= a[great] <= pivot2
  263.                         a[k] = a[great];
  264.                         p[k] = p[great];
  265.                     }
  266.                     /*
  267.                      * Here and below we use "a[i] = b; i--;" instead
  268.                      * of "a[i--] = b;" due to performance issue.
  269.                      */
  270.                     a[great] = ak;
  271.                     p[great] = pk;
  272.                     --great;
  273.                 }
  274.             }
  275.  
  276.             // Swap pivots into their final positions
  277.             a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
  278.             p[left]  = p[less  - 1]; p[less  - 1] = ppivot1;
  279.             a[right] = a[great + 1]; a[great + 1] = pivot2;
  280.             p[right] = p[great + 1]; p[great + 1] = ppivot2;
  281.  
  282.            
  283.             // Sort left and right parts recursively, excluding known pivots
  284.             hackedSort(a, left, less - 2, leftmost);
  285.             hackedSort(a, great + 2, right, false);
  286.  
  287.             /*
  288.              * If center part is too large (comprises > 4/7 of the array),
  289.              * swap internal pivot values to ends.
  290.              */
  291.             if (less < e1 && e5 < great) {
  292.                 throw new RuntimeException();
  293.             }
  294.  
  295.             // Sort center part recursively
  296.             hackedSort(a, less, great, false);
  297.  
  298.         } else { // Partitioning with one pivot
  299.                 throw new RuntimeException();
  300.         }
  301.     }
  302.        
  303.         int maxNum;
  304.         int[] p;
  305.        
  306.         int[] killJava7Quicksort(int n) {
  307.                 maxNum = n;
  308.                 p = new int[n];
  309.                 int[] t = new int[n];
  310.                 for (int i = 0; i < n; i++)     {
  311.                         p[i] = i;
  312.                         t[i] = Integer.MIN_VALUE;
  313.                 }
  314.                 hackedSort(t, 0, n-1, true);
  315.                 validate(p, n, 0, n-1);
  316.                 validate(t, n, 1, n);
  317.                 int[] a = new int[n];
  318.                 for (int i = 0; i < n; i++) {
  319.                         a[p[i]] = t[i];
  320.                 }
  321.                 validate(a, n, 1, n);
  322.                 return a;
  323.         }
  324.        
  325.         void print(int[] a, int n) {
  326.                 out.println(n);
  327.                 for (int i = 0; i < n; i++) {
  328.                         out.print(a[i]);
  329.                         if (i == n-1) out.println(); else out.print(" ");
  330.                 }
  331.         }
  332.  
  333.         void validate(int[] a, int n, int L, int R) {
  334.                 boolean[] used = new boolean[n];
  335.                 for (int x : a) {
  336.                         if (x < L || R < x) {
  337.                                 throw new RuntimeException();
  338.                         }
  339.                         if (used[x - L]) {
  340.                                 throw new RuntimeException();
  341.                         }
  342.                         used[x - L] = true;
  343.                 }
  344.         }
  345.        
  346.         void solve() throws IOException {
  347.                 long t1, t2;
  348.                 int[] a;
  349.                
  350.                 // TODO
  351.                 // 1. enter size of the array to variable n
  352.                 // 2. if property ONLINE_JUDGE is not defined on your local computer it outputs array in file output.txt
  353.                 // 3. don't forget to comment 'System.out.println()' and 'Arrays.sort()' calls before submit
  354.                 // 4. it may not work for some values of n because there's a bug somewhere, so check if sort really works slow before submit
  355.                 int n = 100000;
  356.                
  357.                 {
  358.                         t1 = System.currentTimeMillis();
  359.                         a = killJava7Quicksort(n);
  360.                         t2 = System.currentTimeMillis();
  361.                         System.out.println("Generation takes " + (t2-t1) + " ms");
  362.                 }
  363.                
  364.                 print(a, n);
  365.                
  366.                 {
  367.                         t1 = System.currentTimeMillis();
  368.                         Arrays.sort(a);
  369.                         t2 = System.currentTimeMillis();
  370.                         System.out.println("Sort takes " + (t2-t1) + " ms");
  371.                 }
  372.                
  373.                 System.out.println("Thank you for using Quicksort Killer");
  374.         }
  375.  
  376. }