Robust/src/Benchmarks/SingleTM/Bayes/QuickSort.java

   1 public class QuickSort {
   2   public  QuickSort() {
   3
   4   }
   5
   6   /**
   7    * Sort an array of Objects into ascending order. The sort algorithm is an optimised
   8    * quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
   9    * "Engineering a Sort Function", Software-Practice and Experience, Vol.
  10    * 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
  11    * performance on many arrays that would take quadratic time with a standard
  12    * quicksort.
  13    *
  14    * @param a the array to sort
  15    */
  16   public static void sort(Object[] a)
  17   {
  18     qsort(a, 0, a.length);
  19   }
  20
  21   public static void sort(Object[] a, int fromIndex, int toIndex)
  22   {
  23     qsort(a, fromIndex, toIndex);
  24   }
  25
  26   private static int med3(int a, int b, int c, Object[]d)
  27   {
  28     if(less(d[a], d[b])) {
  29       if(less(d[b], d[c])) {
  30         return b;
  31       } else {
  32         if(less(d[a], d[c]))
  33           return c;
  34         else
  35           return a;
  36       }
  37     } else {
  38       if(less(d[c], d[b])) {
  39         return b;
  40       } else {
  41         if(less(d[c], d[a]))
  42           return c;
  43         else
  44           return a;
  45       }
  46     }
  47   }
  48
  49   private static void swap(int i, int j, Object[] a)
  50   {
  51     Object c = a[i];
  52     a[i] = a[j];
  53     a[j] = c;
  54   }
  55
  56   private static void qsort(Object[] a, int start, int n)
  57   {
  58     // use an insertion sort on small arrays
  59     if (n <= 7)
  60     {
  61       for (int i = start + 1; i < start + n; i++)
  62         for (int j = i; j > 0 && less(a[j], a[j - 1]); j--)
  63           swap(j, j - 1, a);
  64       return;
  65     }
  66
  67     int pm = n / 2;             // small arrays, middle element
  68     if (n > 7)
  69     {
  70       int pl = start;
  71       int pn = start + n - 1;
  72
  73       if (n > 40)
  74       {                     // big arrays, pseudomedian of 9
  75         int s = n / 8;
  76         pl = med3(pl, pl + s, pl + 2 * s, a);
  77         pm = med3(pm - s, pm, pm + s, a);
  78         pn = med3(pn - 2 * s, pn - s, pn, a);
  79       }
  80       pm = med3(pl, pm, pn, a);       // mid-size, med of 3
  81     }
  82
  83     int pa, pb, pc, pd, pv;
  84     int r;
  85
  86     pv = start;
  87     swap(pv, pm, a);
  88     pa = pb = start;
  89     pc = pd = start + n - 1;
  90
  91     while(true)
  92     {
  93       while (pb <= pc && (r = diff(a[pb],a[pv])) <= 0)
  94       {
  95         if (r == 0)
  96         {
  97           swap(pa, pb, a);
  98           pa++;
  99         }
 100         pb++;
 101       }
 102       while (pc >= pb && (r = diff(a[pc],a[pv])) >= 0)
 103       {
 104         if (r == 0)
 105         {
 106           swap(pc, pd, a);
 107           pd--;
 108         }
 109         pc--;
 110       }
 111       if (pb > pc)
 112         break;
 113       swap(pb, pc, a);
 114       pb++;
 115       pc--;
 116     }
 117     int pn = start + n;
 118     int s;
 119     s = Math.imin(pa - start, pb - pa);
 120     vecswap(start, pb - s, s, a);
 121     s = Math.imin(pd - pc, pn - pd - 1);
 122     vecswap(pb, pn - s, s, a);
 123     if ((s = pb - pa) > 1)
 124       qsort(a, start, s);
 125     if ((s = pd - pc) > 1)
 126       qsort(a, pn - s, s);
 127   }
 128
 129   private static void vecswap(int i, int j, int n, Object[] a)
 130   {
 131     for (; n > 0; i++, j++, n--)
 132       swap(i, j, a);
 133   }
 134
 135   /* ===========================================
 136    * compareQuery
 137    * -- Want smallest ID first
 138    * -- For vector_sort
 139    * ===========================================
 140    */
 141   public static boolean less(Object x, Object y) {
 142     Query aQueryPtr = (Query) x;
 143     Query bQueryPtr = (Query) y;
 144     if(aQueryPtr.index < bQueryPtr.index)
 145       return true;
 146     return false;
 147   }
 148
 149   public static int diff(Object x, Object y) {
 150     Query aQueryPtr = (Query) x;
 151     Query bQueryPtr = (Query) y;
 152     return (aQueryPtr.index - bQueryPtr.index);
 153   }
 154
 155   /**
 156    * main to test quick sort
 157    **/
 158   /*
 159   public static void main(String[] args) {
 160     QuickSort qs = new QuickSort();
 161     Query[] queries = new Query[10];
 162
 163     Random r = new Random();
 164     r.random_alloc();
 165     r.random_seed(0);
 166
 167     for(int i = 0; i<10; i++) {
 168       queries[i] = new Query();
 169       queries[i].index = (int) (r.random_generate() % 100);
 170       queries[i].value = -1;
 171     }
 172
 173     System.out.println("Before sorting");
 174     for(int i = 0; i<10; i++)
 175       System.out.println("queries["+i+"]= "+ queries[i]);
 176
 177     qs.sort(queries);
 178
 179     System.out.println("After sorting");
 180     for(int i = 0; i<10; i++)
 181       System.out.println("queries["+i+"]= "+ queries[i]);
 182   }
 183   */
 184 }