|
| 1 | +/** |
| 2 | + * Sorts a sequence of strings from standard input using Quicksort |
| 3 | + * |
| 4 | + * The `QuickSort` class provides static methods for sorting an array and selecting the ith smallest |
| 5 | + * element in an array using quicksort. |
| 6 | + * |
| 7 | + */ |
| 8 | +public class QuickSort { |
| 9 | + private QuickSort() {} |
| 10 | + |
| 11 | + // Rearranges the array in ascending order, using the natural order. |
| 12 | + public static void sort(Comparable[] a) { |
| 13 | + StdRandom.shuffle(a); |
| 14 | + sort(a, 0, a.length - 1); |
| 15 | + assert isSort(a); |
| 16 | + } |
| 17 | + |
| 18 | + // quicksort the subarray from a[low] to a[high] |
| 19 | + private static void sort(Comparable[] a, int low, int high) { |
| 20 | + if(high <= low) |
| 21 | + return; |
| 22 | + int j = partition(a, low, high); |
| 23 | + sort(a, low, j - 1); |
| 24 | + sort(a, j + 1, high); |
| 25 | + assert isSorted(a, low, high); |
| 26 | + } |
| 27 | + |
| 28 | + // partition the subarray a[low, high] so that a[low, ... j - 1] <= a[j] <= a[j + 1, ... high] |
| 29 | + // and return the index j |
| 30 | + private static int partition(Comparable[] a, int low, int high) { |
| 31 | + int i = low; |
| 32 | + int j = high + 1; |
| 33 | + Comparable v = a[low]; |
| 34 | + while(1) { |
| 35 | + while(less(a[++i], v)) { |
| 36 | + if(i == high) |
| 37 | + break; |
| 38 | + } |
| 39 | + // find item on high to swap |
| 40 | + while(less(v, a[--j])) |
| 41 | + if(j == low) |
| 42 | + break; |
| 43 | + if(i >= j) |
| 44 | + break; |
| 45 | + |
| 46 | + exchange(a, i, j); |
| 47 | + } |
| 48 | + |
| 49 | + exchange(a, low, j); |
| 50 | + |
| 51 | + return j; |
| 52 | + } |
| 53 | + |
| 54 | + // rearranges the array so that a[k] contains the kth smallest key; |
| 55 | + // a[0] through a[k - 1] are less than (or equal to) a[k]; and a[k + 1] through a[n - 1] are greater |
| 56 | + // than (or equal to) a[k] |
| 57 | + public static Comparable select(Comparable[] a, int k) { |
| 58 | + if(k < 0 || k >= a.length) |
| 59 | + throw new IllegalArgumentException("index is not between 0 and " + a.length + ": " + k); |
| 60 | + StdRandom.shuffle(a); |
| 61 | + int low = 0, high = a.length - 1; |
| 62 | + while(high >= low) { |
| 63 | + int i = partition(a, low, high); |
| 64 | + if(i > k) |
| 65 | + high = i - 1; |
| 66 | + else if(i < k) |
| 67 | + low = i + 1; |
| 68 | + else |
| 69 | + return a[i]; |
| 70 | + } |
| 71 | + |
| 72 | + return a[low]; |
| 73 | + } |
| 74 | + |
| 75 | + // is v < w ? |
| 76 | + private static boolean less(Comparable v, Comparable w) { |
| 77 | + if(v == w) |
| 78 | + return false; |
| 79 | + return v.compareTo(w) < 0; |
| 80 | + } |
| 81 | + |
| 82 | + // exchange a[i] and a[j] |
| 83 | + private static void exchange(Object[] a, int i, int j) { |
| 84 | + Object swap = a[i]; |
| 85 | + a[i] = a[j]; |
| 86 | + a[j] = swap; |
| 87 | + } |
| 88 | + |
| 89 | + // check if the array is sorted ? |
| 90 | + private static boolean isSorted(Comparable[] a) { |
| 91 | + return isSorted(a, 0, a.length - 1); |
| 92 | + } |
| 93 | + |
| 94 | + private static boolean isSorted(Comparable[] a, int low, int high) { |
| 95 | + for(int i = low + 1; i <= high; i++) |
| 96 | + if(less(a[i], a[i - 1])) |
| 97 | + return false; |
| 98 | + |
| 99 | + return true; |
| 100 | + } |
| 101 | + |
| 102 | + // print the array |
| 103 | + private static void show(Comparable[] a) { |
| 104 | + for(int i = 0; i < a.length; i++) |
| 105 | + StdOut.println(a[i]); |
| 106 | + } |
| 107 | + |
| 108 | + // test |
| 109 | + public static void main(String[] args) { |
| 110 | + String[] a = StdIn.readAllStrings(); |
| 111 | + QuickSort.sort(a); |
| 112 | + show(a); |
| 113 | + |
| 114 | + assert isSorted(a); |
| 115 | + |
| 116 | + StdRandom.shuffle(a); |
| 117 | + |
| 118 | + StdOut.println(); |
| 119 | + for(int i = 0; i < a.length; i++) { |
| 120 | + String ith = (String)QuickSort.select(a, i); |
| 121 | + StdOut.println(ith); |
| 122 | + } |
| 123 | + } |
| 124 | +} |
| 125 | + |
0 commit comments