Quick Sort

Textbook

Description:

Example:

Note

Idea:

• Not stable
• In place
• Time: O(nlogn)

Code:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int partition(vector<int> & nums, int left, int right){
    int i=left-1;

    for(int j=left; j<right; ++j){
        if(nums[j]<=nums[right]){
            swap(nums[++i], nums[j]);
        }
    }
    swap(nums[++i], nums[right]);
    return i;
}

void quickSort(vector<int> & nums, int left, int right){
    if(left<right){
        int pivot = partition(nums, left, right);
        quickSort(nums, left, pivot-1);
        quickSort(nums, pivot+1, right);
    }
}

void quickSort(vector<int> & nums){
    quickSort(nums, 0, nums.size()-1);
}

int main(){
    vector<int> input={3,4,2,5,6,7,2,3,3,8,9,23,43,22,1,23};

    for(auto e: input){
        cout<<e<<' ';
    } cout<<'\n';

    quickSort(input);

    for(auto e: input){
        cout<<e<<' ';
    } cout<<'\n';

}