/** Contains static methods for sorting, together with the methods
* that they use. Included are:
*
* min, to find the minimum of b[h..k].
*
* insertValue, to insert a value into its sorted position in b[h..k-1].
*
* linearSearch, to find a value in an array.
*
* partition0, used in quicksort, as done in class.
*
* partition, used in quicksort, done a bit more efficiently.
*
* medianOf3, used in quicksort.
*
* copy, to return a copy of b[h..k].
*
* merge, used in mergesort.
*
* binarySearch, binary search in an array.
*
* selectionSort, to sort an array.
*
* selectionSort1, to sort an array.
*
* insertionSort, to sort an array.
*
* mergesort, to sort an array recursively.
*
* quicksort0, the basic quicksort algorithm.
*
* quicksort, quicksort changed to fix inefficiencies.
*
* Dutch National Flag.
*
* toString, to create a String that contains elements of an array
* (alternatively, import java.util.Arrays and use Arrays.toString).
*/
public class Sorting {
/** Yields: the position of the minimum value of b[h..k].
* Precondition: h <= k. */
public static int min(int[] b, int h, int k) {
int p= h;
int i= h;
// inv: b[p] is the minimum of b[h..i], i.e.
//
// h-------p------------i---------k
// b | b[p] is min of this | ? |
// --------------------------------
while (i!= k) {
i= i+1;
if (b[i] < b[p]) {
p= i;
}
}
return p;
}
/** Sort b[h..k] --put its elements in ascending order.
* Precondition: b[h..k-1] is sorted, and b[k] contains a value. */
public static void insertValue(int[] b, int h, int k) {
int v= b[k];
int i= k;
/* inv P: (1) Placing v in b[i] makes b[h..k] a
permutation of its initial value
(2) b[h..k] with b[i] removed is initial b[h..k-1]
(3) v < b[i+1..k]
*/
while ((i != h) && v < b[i-1]) {
b[i]= b[i-1];
i= i-1;
}
b[i]= v;
}
/** Yields: index of x in b; or the length of b if x is not in b. */
public static int linearSearch(int[] b, int x) {
// invariant: x is not in b[0..i-1]
int i;
for (i= 0; i != b.length && b[i] != x; i= i+1){}
return i;
}
/** Permute b[h..k] and return integer j satisfying R:<br><br>
*
* b[h..j-1] <= b[j] = x <= b[j+1..k],<br><br>
*
* where x stands for the value initially in b[h].
* Precondition: b[h..k] has at least three elements.
*/
public static int partition0(int[] b, int h, int k) {
//
// h---------------------------k
// pre: b |x| ? | for some x
// -----------------------------
//
// h-------------j-------------k
// post: b | <= x |x| >= x |
// -----------------------------
int j= h;
int i= k;
// inv P: b[h..j-1] <= b[j] = x <= b[i+1..k], i.e.
//
// h---------j-------i------------k
// post: b | <= x |x| ? | >= x |
// --------------------------------
while (j < i) {
if (b[j+1] <= b[j]) {
int temp= b[j]; b[j]= b[j+1]; b[j+1]= temp;
j= j+1;
} else {
int temp= b[j+1]; b[j+1]= b[i]; b[i]= temp;
i= i-1;
}
}
return j;
}
/** Permute b[h..k] and return integer j satisfying R:<br><br>
*
* b[h..j-1] <= b[j] = x <= b[j+1..k]<br><br>
*
* where x stands for the value initially in b[h].
* Precondition: b[h..k] has at least three elements. */
public static int partition(int[] b, int h, int k) {
int j;
// Truthify R1: b[h+1..j] <= b[h] = x <= b[j+1..k];
int i= h+1; j= k;
// inv P: b[h+1..i-1] <= b[h] = x <= b[j+1..k], i.e.
//
//
// h---------i------j----------k
// b |x| <= x | ? | >= x |
// -----------------------------
while (i <= j) {
if (b[i] < b[h]) {
i= i+1;
}
else if (b[j] > b[h]) {
j= j-1;
} else {// b[j] < x < b[i]
int t1= b[i]; b[i]= b[j]; b[j]= t1;
i= i+1; j= j-1;
}
}
int t= b[h]; b[h]= b[j]; b[j]= t;
// R
return j;
}
/** Permute b[h], b[(h+k)/2], and b[k] to put their median in b[h]. */
public static void medianOf3(int[] b, int h, int k) {
int e= (h+k)/2; // index of middle element of array
int m; // index of median
// Return if b[h] is median; else store index of median in m
if (b[h] <= b[e]) {
if (b[h] >= b[k]) return;
// b[h] is smallest of the three
if (b[e] <= b[k]) {
m= e;
} else {
m= k;
}
} else {
if (b[h] <= b[k]) return;
// b[h] is largest of the three
if (b[e] <= b[k]) {
m= k;
} else {
m= e;
}
}
int t= b[h]; b[h]= b[m]; b[m]= t;
}
/** Yields: a copy of array segment b[h..k]. */
public static int[] copy(int[] b, int h, int k) {
int[] c= new int[k+1-h];
// inv: b[h..i-1] has been copied to c[0..i-h-1]
for (int i= h; i != k+1; i= i+1) {
c[i-h]= b[i];
}
return c;
}
/** Sort b[h..k] --put its elements in ascending order.
* Precondition: Segments b[h..e] and b[e+1..k] are already sorted.
*/
public static void merge (int b[], int h, int e, int k) {
int[] c= copy(b,h,e);
// c is a copy of original b[h..e]
int i= h; int j= e+1; int m= 0;
/* inv: b[h..i-1] contains its final, sorted values
b[j..k] remains to be transferred
c[m..e-h] remains to be transferred
*/
for (i= h; i != k+1; i= i+1) {
if (j <= k && (m > e-h || b[j] <= c[m])) {
b[i]= b[j]; j= j+1;
} else {
b[i]= c[m]; m= m+1;
}
}
}
/** Yields: the index i that satisfies R: b[i] <= x < b[i+1].
* Precondition: b is in non-descending order. */
public static int binarySearch(int[] b, int x) {
int i= -1; int j= b.length;
// inv: b[0..i] <= x < b[j..] and -1 <= i < j <= b.length, i.e.
// 0--------i----------j---------- b.length
// b | <=x | ? | >x |
// -------------------------------
while (j != i+1) {
int e= (i+j)/2;
// -1 <= i < e < j <= b.length
if (b[e] <= x) {
i= e;
} else {
j= e;
}
}
return i;
}
/** Sort b: put its elements in ascending order. */
public static void selectionSort(int[] b) {
int j= 0;
// inv P: b[0..j-1] is sorted and b[0..j-1] <= b[j..], i.e.
// 0---------------j--------------- b.length
// inv : b | sorted, <= | >= |
// --------------------------------
while (j != b.length) {
int p= min(b, j, b.length-1);
// b[p] is minimum of b[j..b.length-1]
// Swap b[j] and b[p]
int t= b[j]; b[j]= b[p]; b[p]= t;
j= j+1;
}
}
/** Sort b: put its elements in ascending order. */
public static void selectionSort1(int[] b) {
int j= 0;
// inv P: b[0..j-1] is sorted and b[0..j-1] <= b[j..], i.e.
// 0---------------j--------------- b.length
// inv : b | sorted, <= | >= |
// --------------------------------
while (j != b.length) {
// Put into p the index of smallest element in b[j..]
int p= j;
for (int i= j+1; i != b.length; i++) {
if (b[i] < b[p]) {
p= i;
}
}
// Swap b[j] and b[p]
int t= b[j]; b[j]= b[p]; b[p]= t;
j= j+1;
}
}
/** Sort b[h..k]: put its elements in ascending order. */
public static void insertionSort(int[] b, int h, int k) {
// inv: h <= j <= k+1 and b[h..j-1] is sorted, i.e.
// h---------------j--------------k
// inv : b | sorted, | ? |
// --------------------------------
for (int j= h; j <= k; j= j+1) {
// Sort b[0..j], given that b[0..j-1] is sorted
insertValue(b,0,j);
}
}
/** Sort b[h..k]: put its elements in ascending order. */
public static void mergeSort(int[] b, int h, int k) {
if (h >= k) {
return;
}
int e= (h+k)/2;
mergeSort(b, h, e); // Sort b[h..e]
mergeSort(b, e+1, k); // Sort b[e+1..k]
merge(b, h, e, k); // Merge the 2 segments
}
/** Sort b[h..k] --put its elements in ascending order. */
public static void quickSort0(int[] b, int h, int k) {
if (k+1-h < 2) {
return;
}
int j= partition(b,h,k);
// b[h..j-1] <= b[j] <= b[j+1..k]
quickSort0(b,h,j-1);
quickSort0(b,j+1,k);
}
/** Sort b[h..k]: put its elements in ascending order. */
public static void quickSort(int[] b, int h, int k) {
tailRecursionLoop: while (true) {
if (k+1-h < 10) {
insertionSort(b,h,k);
return;
}
medianOf3(b,h,k);
// b[h] is between b[(h+k)/2] and b[k]
int j= partition(b,h,k);
// b[h..j-1] <= b[j] <= b[j+1..k], i.e.
//
// h---------j---------k
// b | <= x |x| >= x | for some x
// ---------------------
if (j-h <= k-j) {
quickSort(b,h,j-1);
// quicksort(b,j+1,k);
h= j+1;
continue tailRecursionLoop;
}
else {
quickSort(b,j+1,k);
// quicksort(b,h,j-1);
k= j-1;
continue tailRecursionLoop;
}
} // tailRecursionLoop
}
/** Swap the values of b so that the negative ones are
* first, then the 0's, and finally the positive ones.
* In the original problem, the negative values are red
* balls, 0's are white balls, positive values are blue balls*/
public static void DutchNationalFlag(int[] b) {
// 0------------------------------------ b.length
// pre: b| ? |
// -------------------------------------
//
// 0------------------------------------ b.length
// post:b| <0 | = 0 | >0 |
// -------------------------------------
int h= 0;
int k= 0;
int t= b.length-1;
// 0-------h-------k------t------------- b.length
// inv :b| <0 | = 0 | ? | >0 |
// -------------------------------------
while (k <= t) {
if (b[k] < 0) {
int temp= b[k]; b[k]= b[h]; b[h]= temp;
h= h+1; k= k+1;
} else if (b[k] == 0) {
k= k+1;
} else {
int temp= b[k]; b[k]= b[t]; b[t]= temp;
t= t-1;
}
}
}
/** Yields: values of b, separated by ", " and with
* the whole list delimited by "[" and "]".
*/
public static String toString(int[] b) {
String res= "[";
// inv: res contains b[0..k-1], with "[" at
// beginning and values separated by ", "
for (int k= 0; k != b.length; k= k+1) {
if (k != 0)
res= res + ", ";
res= res + b[k];
}
return res + "]";
}
}