1 /**
2 The sort method of this class sorts an array, using the quick
3 sort algorithm.
4 */
5 public class QuickSorter
6 {
7 /**
8 Sorts an array, using quick sort.
9 @param a the array to sort
10 */
11 public static void sort(int[] a)
12 {
13 sort(a, 0, a.length - 1);
14 }
15
16 /**
17 Sorts a portion of an array, using quick sort.
18 @param a the array to sort
19 @param from the first index of the portion to be sorted
20 @param to the last index of the portion to be sorted
21 */
22 public static void sort(int[] a, int from, int to)
23 {
24 if (from >= to) { return; }
25 int p = partition(a, from, to);
26 sort(a, from, p);
27 sort(a, p + 1, to);
28 }
29
30 /**
31 Partitions a portion of an array.
32 @param a the array to partition
33 @param from the first index of the portion to be partitioned
34 @param to the last index of the portion to be partitioned
35 @return the last index of the first partition
36 */
37 private static int partition(int[] a, int from, int to)
38 {
39 int pivot = a[from];
40 int i = from - 1;
41 int j = to + 1;
42 while (i < j)
43 {
44 i++; while (a[i] < pivot) { i++; }
45 j--; while (a[j] > pivot) { j--; }
46 if (i < j) { ArrayUtil.swap(a, i, j); }
47 }
48 return j;
49 }
50 }