package me.alivecode.algs4;

import edu.princeton.cs.algs4.StdIn;

public class Quick {

    private Quick() {}

    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 no lo to swap
            while(SortUtil.less(a[++i], v)) { 
                if (i >= hi) break;
            }
            // find item on hi to swap
            while(SortUtil.less(v, a[--j])) {
                if (j <= lo) break;  // randundant since a[lo] acts as sentinel. BUT WHY?
            }
            
            if (i >= j) break; // check if pointers cross.
            SortUtil.exch(a, i, j);
        }
        SortUtil.exch(a, lo, j);

        return j;
    }

    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 SortUtil.isSorted(a, lo, hi);
    }

    public static void sort(Comparable[] a) {
        assert (a != null && a.length > 0);
        StdRandom.shuffle(a);
        sort(a, 0, a.length-1);
        assert SortUtil.isSorted(a);
    }

    public static void main(String[] args) {
        String[] a = StdIn.readAllStrings();
        sort(a);
        SortUtil.show(a);
    }
} 

@@ -58,16 +58,54 @@
 4.StdIn;
+%0Aimport edu.princeton.cs.algs4.StdOut;
 %0A%0Apublic
@@ -622,16 +622,45 @@
 el. 
-BUT WHY?
+v=a%5Blo%5D, will never less than a%5Blo%5D; 
 %0A   
@@ -1197,24 +1197,71 @@
 .shuffle(a);
+ // a random array is critical for performance.
 %0A        sor
@@ -1333,142 +1333,1031 @@
     
-public static void main(String%5B%5D args) %7B%0A        String%5B%5D a = StdIn.readAllStrings();%0A        sort(a);%0A        SortUtil.show(a);
+// find the kth smallest item in an unordered array.%0A    // The array divided into 2 part, a%5Blo, j-1%5D %3C a%5Bj%5D %3C a%5Bj+1, hi%5D%0A    // and the kth smallest item will fall in one of the two part or it is just a%5Bj%5D.%0A    public static Comparable selection(Comparable%5B%5D a, int k) %7B%0A        int lo = 0;%0A        int hi = a.length - 1;%0A        StdRandom.shuffle(a);%0A        while(hi %3E lo) %7B %0A            int j = partition(a, lo, hi);%0A            if (j %3E k) %7B%0A                hi = j - 1;%0A            %7D%0A            else if (j %3C k) %7B%0A                lo = j + 1;%0A            %7D%0A            else %7B%0A               return a%5Bk%5D; // a%5Bk%5D is not in the left part nor right part. It is the kth smallest item.%0A            %7D%0A        %7D%0A        return a%5Bk%5D;%0A    %7D %0A%0A            %0A    public static void main(String%5B%5D args) %7B%0A        String%5B%5D a = StdIn.readAllStrings();%0A        sort(a);%0A        SortUtil.show(a);%0A        int k = Integer.parseInt(args%5B0%5D);%0A        selection(a, k);%0A        StdOut.printf(%22The %25dth smallest item is %25s%5Cn%22, k, a%5Bk%5D);%0A
 %0A    %7D%0A%7D
  %0A
@@ -2354,10 +2354,9 @@
 %0A    %7D%0A%7D
- 
 %0A

Add quick sort and quick select.