Quick Select & Quick Sort

Summary

Quick Select is typical technique to select the top k elements (the rest of array is not sorted) from an array in amortized O(n) time. If we use a smart way to choose pivot (Introselect), the algorithm is guaranteed to have O(n) worst case performance.

Quick Sort is an unstable sort. It has amortized O(nlogn) and worst case O(n^2) complexity. Introsort combines Quick Sort and Heap Sort and is guaranteed to have O(nlogn) worst case performance.

A handy template function in the standard library is shown blow.

template <class RandomAccessIterator, class Compare>
  void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
                    RandomAccessIterator last, Compare comp);
// iterator before nth has smaller or equal value; iterator after nth has larger or equal value
// nth_element(nums.begin(), nums.begin()+k-1, nums.end())
// nums[k-1] will be the kth smallest number. 

If we want to use the pivot and divide and conquer technique to implement both Quick Select and Sort. Common techniques to avoid infinite loop or wrong answers are listed below.

1. Choose left as the pivot;
2. loop while left < right (not <=);
3. Move right pointer first;
4. Decrease right only if left is still < right;

Quick Select

int quick_select(int left, int right, int k, vector<int>& nums) {
    int pivot = left;
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[pivot]) {
            j--;
        }
        while (i < j && nums[i] <= nums[pivot]) {
            i++;
        }
        if (i == j) {
            break;
        }
        swap(nums[i], nums[j]);
        j--;
    }
    swap(nums[pivot], nums[i]);
    if (i - pivot + 1 == k) {
        return nums[i];
    } else if (i - pivot + 1 > k) {
        return quick_select(left, i - 1, k, nums);
    } else {
        return quick_select(i + 1, right, k - (i - pivot + 1), nums);
    }
}

This implementation has the following complexity.

1. amortized O(n)
2. worst case O(n^2) (given an array with all same values and k==n; in this case, each time the array only shrinks by one element)

Quick Sort

void quick_sort(int left, int right, vector<int>& nums) {
    if (left >= right) {
        return;
    }
    int pivot = left;
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[pivot]) {
            j--;
        }
        while (i < j && nums[i] <= nums[pivot]) {
            i++;
        }
        if (i == j) {
            break;
        }
        swap(nums[i], nums[j]);
        j--;
    }
    swap(nums[pivot], nums[i]);
    quick_sort(left, i - 1, nums);
    quick_sort(i + 1, right, nums);
}

This implementation has the following complexity.

1. amortized O(nlogn)
2. worst case O(n^2) (given an sorted array; in this case, each time the array only shrinks by one element)