11. Quick3 Sort

Quick3 sort solves some problems with quick sort, the issue of all of the elements equalling each other, for example. It works by partitioning all of the elements smaller than pivot, the elements equal to the pivot, and elements greater than pivot.

public <T extends Comparable<? super T>> void quick3Sort(T[] array) {
    quick3SortHelper(array, 0, array.length - 1);
}

private <T extends Comparable<? super T>> void quick3SortHelper(T[] array, int low, int high) {
    if (low < high) {
        int[] pivot = partition3(array, low, high);
        quick3SortHelper(array, low, pivot[1]);
        quick3SortHelper(array, pivot[0], high);
    }
}

private <T extends Comparable<? super T>> int[] partition3(T[] array, int low, int high) {
    int i = low - 1;
    int j = high;
    int p = low - 1; 
    int q = high;
    T pivot = array[high];

    while(true) {
        while(array[++i].compareTo(pivot) < 0);

        while(pivot.compareTo(array[--j]) < 0) {
            if (j == low) {
                break;
            }
        }

        if (i >= j) {
            break;
        }

        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;

        if (array[i].compareTo(pivot) == 0) {
            p++;
            temp = array[i];
            array[i] = array[p];
            array[p] = temp;
        }

        if (array[j].compareTo(pivot) == 0) {
            q--;
            temp = array[q];
            array[q] = array[j];
            array[j] = temp;
        }
    }   

    T temp = array[i];
    array[i] = array[high];
    array[high] = temp;

    j = i - 1;
    for (int k = low; k < p; k++, j--) {
        temp = array[k];
        array[k] = array[j];
        array[j] = temp;
    }

    i = i + 1;
    for (int k = high - 1; k > q; k--, i++) {
        temp = array[i];
        array[i] = array[k];
        array[k] = temp;
    }

    int[] x = { i, j };

    return x;
}

Quick3 sort has a worst case runtime of $O(n^2)$, but an average case runtime of $\Theta(nlog(n))$. It's space complexity is $O(log(n))$.

Next Page →