Quick Sort

Introduction

We already have seen the worst case O(nlogn) merge sort algorithm. But for merge sort, we need O(n) extra space to implement (at least in practice). Is there an O(nlogn) sorting algorithm that uses constant space?

Question (LC.464)

Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.

Analysis

merge sort T(n) = 2T(n/2) + n (merge results in the end)

quick sort is T(n) = n + 2T(n/2) (partition before conquer recursively)

Code

public class Solution {
    public void sortIntegers(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        quickSort(A, 0, A.length - 1);
    }

    private void quickSort(int[] A, int start, int end) {
        // base case one element just return it
        // not always one there can be zero elements
        if (start >= end) {
            return;
        }

        // divide
        // we just select a random pivot in the middle
        // in a way QS is a randomized algorithm
        // the expected (averge) runtime is good
        // but worst case can happen in a small likelihood
        int pivot = A[start + (end - start) / 2];

        // need to partition first (unlike merge sort does this in the end)
        int left = start, right = end;
        while (left <= right) {
            // why not <= here? think about worst case [1,1,1,1,1]
            if (A[left] < pivot) {
                left++;
            } else if (A[right] > pivot) {
                right--;
            } else {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;
                left++;
                right--;
            }
        }

        // conquer
        // QS(A[start...right])
        // (cause to break the while loop left&right have to cross each other)
        quickSort(A, start, right);
        quickSort(A, left, end);

        // merge
        // we already did this in partition
    }
}

Trace an example where there is zero element then return. [3,2,1,4,5]

Checkout another way to implement partition. q = partition(A[start...end])

With Simple Partition

public void sortIntegers2(int[] A) {
    if (A == null || A.length <= 1) {
        return;
    }
    quickSort(A, 0, A.length - 1);
}

public void quickSort(int[] arr, int start, int end) {
    // base case
    if (start >= end) {
        return;
    }
    // divide
    int pivotPos = partition(arr, start, end);
    // conquer
    quickSort(arr, start, pivotPos - 1);
    quickSort(arr, pivotPos + 1, end);
}

private int partition(int[] arr, int start, int end) {
    int pivot = arr[start];
    int left = start + 1, right = end;
    while (left <= right) {
        while (left <= right && arr[left] < pivot) {
            left++;
        }
        while (left <= right && arr[right] >= pivot) {
            right--;
        }
        if (left <= right) {
            swap(arr, left, right);
            left++;
            right--;
        }
    }
    // swap pivot with the last value < pivotValue
    swap(arr, start, right);
    return right;
}

Conclusion

Quick sort is in-place. But unlike merge sort, quick sort does not preserve the stable property of the array.