Princeton1/module7/src/main/java/com/hithomelabs/princeton1/module7/Quick.java

package com.hithomelabs.princeton1.module7;

import com.hithomelabs.princeton1.module5.AbstractCustomSorts;


public class Quick<E> extends AbstractCustomSorts<E> {
    @Override
    public void sort(E[] arr) {
        int N = arr.length;
        quickSort(arr, 0, N - 1);
    }

    public void altSort(E[] arr) {
        int N = arr.length;
        altQuickSort(arr, 0, N-1);
    }

    private void altQuickSort(E[] arr, int lo, int hi) {
        if (lo >= hi) return;
        int i = lo + 1;
        int j = i;
        while(j <= hi){
            if(less((Comparable<E>) arr[j], arr[lo])){
                exch(arr, i, j);
                i++;
            }
            j++;
        }
        exch(arr, i-1, lo);
        altQuickSort(arr, lo, i-2);
        altQuickSort(arr, i, hi);
    }

    private void quickSort(E[] arr, int lo, int hi) {

        if (lo >= hi) return;
        int i = lo;
        int j = hi+1;
        while(true){
            while(less((Comparable<E>) arr[++i], arr[lo])){
                if(i == hi) break;
            }
            while(!less((Comparable<E>) arr[--j], arr[lo])){
                if (j == lo ) break;
            }
            if(j<=i) break;
            exch(arr, i , j);
        }
        exch(arr, j, lo);
        quickSort(arr, lo, j-1);
        quickSort(arr, j+1, hi);

    }
}