package com.varunvats.practice.sorting;

import edu.princeton.cs.algs4.StdRandom;

public class Quick extends SortBase {

    private Quick() {
        // This class cannot be instantiated.
    }

    public static <T extends Comparable<T>> void sort(T[] a) {
        final int N = a.length;
        StdRandom.shuffle(a);
        createSentinel(a);
        sort(a, 0, N - 1);
    }

    private static <T extends Comparable<T>> void sort(T[] a, int low, int high) {
        if (low >= high)
            return;
        final int j = partition(a, low, high);
        sort(a, low, j - 1);
        sort(a, j + 1, high);
    }

    private static <T extends Comparable<T>> int partition(T[] a, int low, int high) {
        final T v = a[low];
        int leftCursor = low;
        int rightCursor = high + 1;
        while (true) {
            while (less(a[++leftCursor], v)) {
            }
            while (less(v, a[--rightCursor])) {
            }
            if (leftCursor >= rightCursor)
                break;
            exchange(a, leftCursor, rightCursor);
        }
        exchange(a, low, rightCursor);
        return rightCursor;
    }

    private static <T extends Comparable<T>> void createSentinel(T[] a) {
        final int N = a.length;
        if (N > 1) {
            final int maxValueIndex = getMaxValueIndex(a);
            exchange(a, maxValueIndex, N - 1);
        }
    }

    private static <T extends Comparable<T>> int getMaxValueIndex(T[] a) {
        int maxValueIndex = 0;
        for (int i = 1; i < a.length; i++)
            if (less(a[maxValueIndex], a[i]))
                maxValueIndex = i;
        return maxValueIndex;
    }
}

@@ -817,24 +817,85 @@
 le (true) %7B%0A
+            do %7B%0A                ++leftCursor;%0A            %7D%0A
             
@@ -908,18 +908,16 @@
 (less(a%5B
-++
 leftCurs
@@ -924,18 +924,66 @@
 or%5D, v))
- %7B
+;%0A%0A            do %7B%0A                --rightCursor;
 %0A       
@@ -1018,18 +1018,16 @@
 ss(v, a%5B
---
 rightCur
@@ -1036,24 +1036,10 @@
 r%5D))
- %7B%0A            %7D
+;%0A
 %0A   

Make intention in Quick sort inner loop clearer.