1   package kiasan.examples.sort;
2   
3   public final class Sort {
4     private static final int CUTOFF = 10;
5   
6     /**
7      * Quick selection algorithm. Places the kth smallest item in a[k-1].
8      * 
9      * @param a
10     *          an array of Comparable items.
11     * @param k
12     *          the desired rank (1 is minimum) in the entire array.
13     */
14  
15    /**
16     * Standard heapsort.
17     * 
18     */
19    //@ requires a != null;
20    //@ ensures Sort.isSorted(a);
21    public static void heapSort(final int[] a) {
22      /* 1 */for (int i = a.length / 2 - 1; i >= 0; i--) {
23        /* 2 */Sort.percDown(a, i, a.length);
24      }
25      /* 3 */for (int i = a.length - 1; i > 0; i--) {
26        /* 4 */Sort.swap(a, 0, i); /* deleteMax */
27        /* 5 */Sort.percDown(a, 0, i);
28      }
29    }
30  
31    //@ requires a != null;
32    //@ ensures Sort.isSorted(a);
33    public static void insertionSort(final int[] a) {
34      int j;
35  
40        }
42      }
44  
45    /**
46     * Internal insertion sort routine for subarrays that is used by quicksort.
47     * 
48     * @param a
49     *          an array of Comparable items.
50     * @param left
51     *          the left-most index of the subarray.
52     * @param right
53     *          the right-most index of the subarray.
54     */
55    private static void insertionSort(final int[] a, final int left,
56        final int right) {
57      for (int p = left + 1; p <= right; p++) {
58        final int tmp = a[p];
59        int j;
60  
61        for (j = p; (j > left) && (tmp < a[j - 1]); j--) {
62          a[j] = a[j - 1];
63        }
64        a[j] = tmp;
65      }
66    }
67  
68    static boolean isSorted(final int[] a) {
71          return false;
72        }
73      }
75    }
76  
77    /**
78     * Internal method for heapsort.
79     * 
80     * @param i
81     *          the index of an item in the heap.
82     * @return the index of the left child.
83     */
84    private static int leftChild(final int i) {
85      return 2 * i + 1;
86    }
87  
88    /**
89     * Return median of left, center, and right. Order these and hide the pivot.
90     */
91    private static int median3(final int[] a, final int left, final int right) {
92      final int center = (left + right) / 2;
93      if (a[center] < a[left]) {
94        Sort.swap(a, left, center);
95      }
96      if (a[right] < a[left]) {
97        Sort.swap(a, left, right);
98      }
99      if (a[right] < a[center]) {
100       Sort.swap(a, center, right);
101     }
102 
103     // Place pivot at position right - 1
104     Sort.swap(a, center, right - 1);
105     return a[right - 1];
106   }
107 
108   /**
109    * Internal method for heapsort that is used in deleteMax and buildHeap.
110    * 
111    * @param a
112    *          an array of Comparable items.
113    * @index i the position from which to percolate down.
114    * @int n the logical size of the binary heap.
115    */
116   private static void percDown(final int[] a, int i, final int n) {
117     int child;
118     int tmp;
119 
120     /* 1 */for (tmp = a[i]; Sort.leftChild(i) < n; i = child) {
121       /* 2 */child = Sort.leftChild(i);
122       /* 3 */if ((child != n - 1) && (a[child] < a[child + 1])) {
123         /* 4 */child++;
124       }
125       /* 5 */if (tmp < a[child]) {
126         /* 6 */a[i] = a[child];
127       } else {
128         /* 7 */break;
129       }
130     }
131     /* 8 */a[i] = tmp;
132   }
133 
134   /**
135    * Quicksort algorithm.
136    * 
137    * @param a
138    *          an array of Comparable items.
139    */
140   public static void quicksort(final int[] a) {
141     Sort.quicksort(a, 0, a.length - 1);
142   }
143 
144   /**
145    * Internal quicksort method that makes recursive calls. Uses median-of-three
146    * partitioning and a cutoff of 10.
147    * 
148    * @param a
149    *          an array of Comparable items.
150    * @param left
151    *          the left-most index of the subarray.
152    * @param right
153    *          the right-most index of the subarray.
154    */
155   private static void quicksort(final int[] a, final int left, final int right) {
156     /* 1 */if (left + Sort.CUTOFF <= right) {
157       /* 2 */final int pivot = Sort.median3(a, left, right);
158 
159       // Begin partitioning
160       /* 3 */int i = left, j = right - 1;
161       /* 4 */for (;;) {
162         /* 5 */while (a[++i] < pivot) {
163         }
164         /* 6 */while (a[--j] > pivot) {
165         }
166         /* 7 */if (i < j) {
167           /* 8 */Sort.swap(a, i, j);
168         } else {
169           /* 9 */break;
170         }
171       }
172 
173       /* 10 */Sort.swap(a, i, right - 1); // Restore pivot
174 
175       /* 11 */Sort.quicksort(a, left, i - 1); // Sort small elements
176       /* 12 */
177       Sort.quicksort(a, i + 1, right); // Sort large elements
178     } else {
179       /* 13 */Sort.insertionSort(a, left, right);
180     }
181   }
182 
183   //@ requires x != null;
184   //@ ensures Sort.isSorted(x);
185   public static void selectionSort(final int[] x) {
189           //... Exchange elements
193         }
194       }
195     }
197 
198   public static final void swap(final int[] a, final int index1,
199       final int index2) {
200     final int tmp = a[index1];
201     a[index1] = a[index2];
202     a[index2] = tmp;
203   }
204 
205   /**
206    * Method to swap to elements in an array.
207    * 
208    * @param a
209    *          an array of objects.
210    * @param index1
211    *          the index of the first object.
212    * @param index2
213    *          the index of the second object.
214    */
215   public static final void swapReferences(final Object[] a, final int index1,
216       final int index2) {
217     final Object tmp = a[index1];
218     a[index1] = a[index2];
219     a[index2] = tmp;
220   }
221 
222   /**
223    * Shellsort, using Shell's (poor) increments.
224    * 
225    * @param a
226    *          an array of Comparable items.
227    */
228   //@ requires a != null;
229   //@ ensures Sort.isSorted(a);
230   public void shellsort(final int[] a) {
231     int j;
232 
238         }
240       }
241     }
243 }