10. Quick Sort

Quick sort uses array partitions by placing a pivot and placing elements to the left side of the partition if the element is less than the pivot or to the right side of the partition if the element if more than the pivot. Then, this process if preformed again on each partition until the array is fully sorted. How we choose our pivot can greatly affect the speed of the algorithm, some of the ways of choosing a pivot includes picking the first element, the last element, a random element, the middle or some other way of choosing a pivot.

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

private <T extends Comparable<? super T>> void quickSortHelper(T[] array, int low, int high) {
    if (low < high) {
        int pivot = partition(array, low, high);
        quickSortHelper(array, low, pivot - 1);
        quickSortHelper(array, pivot + 1, high);
    }
}

private <T extends Comparable<? super T>> int partition(T[] array, int low, int high) {
    T pivot = array[high];
    // To make this random, you would simply select a random index from low to high.
    // either way is fine, random helps guarantee half of the elements will provide a
    // balanced partition
    int i = low - 1;

    for(int j = low; j <= high - 1; j++) {
        if (array[j].compareTo(pivot) < 0) {
            i++;
            T temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    T temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;

    return i + 1;
}

What is the probability of two elements being compared with a random quick sort?

To not get technical and to keep it simple, the probably of elements $i$ and $j$ being indexes in sorted order and compared with quick sort is:

$$Prob(\chi_{ij}) = \frac{2}{j-i+1}$$

Quick sort has a worst case runtime of $O(n^2)$ (with bad pivots), but an average case runtime of $\Theta(nlog(n))$. It's space complexity is $O(log(n))$. This makes quick sort very good, as it has both good time and space complexities.

Las Vegas and Monte Carlo

Some algorithms, quick sort, has some type of chance to them. A Las Vegas algorithm is always correct, but may have a bad runtime. A Monte Carlo algorithm has the same runtimes, but may produce incorrect output (very small probability of happening). Quick sort is a Las Vegas algorithm.

Next Page →