Robust/src/Benchmarks/SingleTM/Labyrinth/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 void sort(Object[] a)
  17   {
  18     qsort(a, 0, a.length);
  19   }
  20
  21   public void sort(Object[] a, int fromIndex, int toIndex)
  22   {
  23     qsort(a, fromIndex, toIndex);
  24   }
  25
  26   private 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 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 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 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   public boolean less(Object x, Object y) {
 136     Query aQueryPtr = (Query) x;
 137     Query bQueryPtr = (Query) y;
 138     if(aQueryPtr.index < bQueryPtr.index)
 139       return true;
 140     return false;
 141   }
 142
 143   public int diff(Object x, Object y) {
 144     Query aQueryPtr = (Query) x;
 145     Query bQueryPtr = (Query) y;
 146     return (aQueryPtr.index - bQueryPtr.index);
 147   }
 148
 149   /**
 150    * main to test quick sort
 151    **/
 152   /*
 153   public static void main(String[] args) {
 154     QuickSort qs = new QuickSort();
 155     Query[] queries = new Query[10];
 156
 157     Random r = new Random();
 158     r.random_alloc();
 159     r.random_seed(0);
 160
 161     for(int i = 0; i<10; i++) {
 162       queries[i] = new Query();
 163       queries[i].index = (int) (r.random_generate() % 100);
 164       queries[i].value = -1;
 165     }
 166
 167     System.out.println("Before sorting");
 168     for(int i = 0; i<10; i++)
 169       System.out.println("queries["+i+"]= "+ queries[i]);
 170
 171     qs.sort(queries);
 172
 173     System.out.println("After sorting");
 174     for(int i = 0; i<10; i++)
 175       System.out.println("queries["+i+"]= "+ queries[i]);
 176   }
 177   */
 178 }