Below is the syntax highlighted version of Quick.java.
/****************************************************************************** * Compilation: javac Quick.java * Execution: java Quick < input.txt * Dependencies: StdOut.java StdIn.java * Data files: https://algs4.cs.princeton.edu/23quicksort/tiny.txt * https://algs4.cs.princeton.edu/23quicksort/words3.txt * * Sorts a sequence of strings from standard input using quicksort. * * % more tiny.txt * S O R T E X A M P L E * * % java Quick < tiny.txt * A E E L M O P R S T X [ one string per line ] * * % more words3.txt * bed bug dad yes zoo ... all bad yet * * % java Quick < words3.txt * all bad bed bug dad ... yes yet zoo [ one string per line ] * * * Remark: For a type-safe version that uses static generics, see * * https://algs4.cs.princeton.edu/23quicksort/QuickPedantic.java * ******************************************************************************/ package edu.princeton.cs.algs4; /** * The {@code Quick} class provides static methods for sorting an * array and selecting the ith smallest element in an array using quicksort. * <p> * For additional documentation, see * <a href="https://algs4.cs.princeton.edu/23quicksort">Section 2.3</a> * of <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class Quick { // This class should not be instantiated. private Quick() { } /** * Rearranges the array in ascending order, using the natural order. * @param a the array to be sorted */ public static void sort(Comparable[] a) { StdRandom.shuffle(a); sort(a, 0, a.length - 1); assert isSorted(a); } // quicksort the subarray from a[lo] to a[hi] private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) return; int j = partition(a, lo, hi); sort(a, lo, j-1); sort(a, j+1, hi); assert isSorted(a, lo, hi); } // partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi] // and return the index j. private static int partition(Comparable[] a, int lo, int hi) { int i = lo; int j = hi + 1; Comparable v = a[lo]; while (true) { // find item on lo to swap while (less(a[++i], v)) { if (i == hi) break; } // find item on hi to swap while (less(v, a[--j])) { if (j == lo) break; // redundant since a[lo] acts as sentinel } // check if pointers cross if (i >= j) break; exch(a, i, j); } // put partitioning item v at a[j] exch(a, lo, j); // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi] return j; } /** * Rearranges the array so that {@code a[k]} contains the kth smallest key; * {@code a[0]} through {@code a[k-1]} are less than (or equal to) {@code a[k]}; and * {@code a[k+1]} through {@code a[n-1]} are greater than (or equal to) {@code a[k]}. * * @param a the array * @param k the rank of the key * @return the key of rank {@code k} * @throws IllegalArgumentException unless {@code 0 <= k < a.length} */ public static Comparable select(Comparable[] a, int k) { if (k < 0 || k >= a.length) { throw new IllegalArgumentException("index is not between 0 and " + a.length + ": " + k); } StdRandom.shuffle(a); int lo = 0, hi = a.length - 1; while (hi > lo) { int i = partition(a, lo, hi); if (i > k) hi = i - 1; else if (i < k) lo = i + 1; else return a[i]; } return a[lo]; } /*************************************************************************** * Helper sorting functions. ***************************************************************************/ // is v < w ? private static boolean less(Comparable v, Comparable w) { if (v == w) return false; // optimization when reference equals return v.compareTo(w) < 0; } // exchange a[i] and a[j] private static void exch(Object[] a, int i, int j) { Object swap = a[i]; a[i] = a[j]; a[j] = swap; } /*************************************************************************** * Check if array is sorted - useful for debugging. ***************************************************************************/ private static boolean isSorted(Comparable[] a) { return isSorted(a, 0, a.length - 1); } private static boolean isSorted(Comparable[] a, int lo, int hi) { for (int i = lo + 1; i <= hi; i++) if (less(a[i], a[i-1])) return false; return true; } // print array to standard output private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.println(a[i]); } } /** * Reads in a sequence of strings from standard input; quicksorts them; * and prints them to standard output in ascending order. * Shuffles the array and then prints the strings again to * standard output, but this time, using the select method. * * @param args the command-line arguments */ public static void main(String[] args) { String[] a = StdIn.readAllStrings(); Quick.sort(a); show(a); assert isSorted(a); // shuffle StdRandom.shuffle(a); // display results again using select StdOut.println(); for (int i = 0; i < a.length; i++) { String ith = (String) Quick.select(a, i); StdOut.println(ith); } } } /****************************************************************************** * Copyright 2002-2022, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/