quick sort - cocoder39/coco39_LC GitHub Wiki

key words: array, comparison sort, unstable. average time is O(n * log n), worst time is O(n ^ 2) when partition is unbalanced (1 vs n-1 -> 1 vs n-2). The space complexity is from recursion stack, which is O(log n) on avg but O(n) in the worst case.

reference https://www.interviewbit.com/tutorial/quicksort-algorithm/#:~:text=Space%20Complexity%20of%20Quick%20sort,order%20O(log%20n)%20.

  • choice of pivot

choose min/max value from an already sorted causes worst-case. One better way is choosing the median of first, middle and last element. a even stronger tule, for larger arrays, is to pick median(median(first 1/3), median(middle 1/3), median(final 1/3))

  • repeated elements

when all elements are equal, at each recursion, left partition is empty and right partition decrease by only one element. Hence time is O(n ^ 2). To solve this problem, a O(n) partition routine can separated the elements into three groups: less than pivot, equal to pivot, and greater than pivot. so only less-than and greater-than partitions need to be recursively sorted. In this way, we modify partition routine, which returns less-than index and greater-than index.

  • worst case

worst case occurs when the pivot divides the list into two sublists of size 0 and n - 1. It happens if pivot is the min/max element, or all elements are equal

  • average case

T(n) = 2T(n/2) + O(n) = O(n * log n)

  • space complexity

in place sort an array, if O(log n) because of recursion call stack.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int partition(vector<int>& a, int low, int high) {
    int i = low;
    int j = high + 1;
    while (true) {
        while (a[++i] <= a[low]) {
            if (i == high) {
                break;
            }
        }
        while (a[--j] >= a[low]) {
            if(j == low){
                break;
            }
        }
        if (i >= j) {
            break;
        }
        swap(a[i], a[j]);
    }
    swap(a[low], a[j]);
    return j;
}

int partition_t(vector<int>& a, int low, int high) {
  //a[high] is pivot
  //find elements smaller than pivot, swap to left side  
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (a[j] < a[high]) {
            i++;
            swap(a[i], a[j]); // a[0]...a[i] are less than pivot
        }
    }
    swap(a[i + 1], a[high]);
    return i + 1;
}
 
// find kth smallest element 
// change partition strategy or k=a.size()-k+1 when finding kth greatest element
int quickSelect(vector<int>& a, int k) {
    int low = 0;
    int high = a.size() - 1;
    while (low < high) {
        int p = partition(a, low, high);
        if (p < k - 1) {
            low = p + 1;
        }
        else if (p > k - 1) {
            high = p - 1;
        }
        else { // p == k - 1
            return a[p];
        }
    }
    return a[k - 1];
}

void qs_helper(vector<int>& a, int low, int high) {
    if (low >= high) {
        return;
    }
    int p = partition(a, low, high);
    qs_helper(a, low, p);
    qs_helper(a, p + 1, high);
}

void quickSort(vector<int>& a) {
    int sz = a.size();
    if (sz <= 1) {
        return;
    }
    qs_helper(a, 0, sz - 1);
}

int main(){
    vector<int> a{7, 8, 30, 4, 5, 8, 19};
    cout << quickSelect(a, 7) << endl;
    return 0;
}
⚠️ **GitHub.com Fallback** ⚠️