Author:
Quick Sort⚓︎
Keywords: Sorting
Description⚓︎
Quick Sort?
Quick Sort
is a sorting method that implements the divide and conquer
idea.
The related Quickselect
algorithm is known as Hoare's selection algorithm, developed by Tony Hoare.
Efficiency?
Average time complexity: \(O(n\log n)\)
Worst time complexity: \(O(n^2)\)
Algorithm Details⚓︎
Steps
Step1. "Pivot": pick a pivot
in the array. We normally pick the most left element.
Step2. "Partition": scan the whole array. Compare the scanned element with the pivot
:
element > pivot
-> move the right part, get the right part.element < pivot
-> move the left part, get the left part.
Step3. "Recursive": redo left and right parts separately with Step1 and Step2.
Diagram⚓︎
Answer⚓︎
Realization
solution.c++
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;
//partition
int partitionArray(vector<int> &nums, int low, int high){
if(low >= high) return -1;
int pivot = low, l = pivot + 1, r = high;
while(l <= r){
if(nums[l] < nums[pivot]) l++;
else if(nums[r] >= nums[pivot]) r--; // larger and equal are all located at the right side
else swap(nums[l], nums[r]);
}
swap(nums[pivot], nums[r]);
return r;
}
//recursive body
void quickSort(vector<int> &nums, int low, int high){
if(low >= high) return;
swap(nums[low + rand() % (high - low + 1)], nums[low]);
int pivot = partitionArray(nums, low, high);
quickSort(nums,low, pivot);
quickSort(nums,pivot+1, high);
}
int main()
{
vector<int> input = {4,1,5,3,6};
//cout<<"input:";
//for(auto i: input)
//{
// if(i==input.back()){
// cout<<i<<endl;
// }
// else cout<<i<<",";
//}
quickSort(input,0,input.size()-1);
vector<int> test = {1,3,4,5,6};
assert(output == test);
//cout<<"output:";
//for(auto i: input)
//{
// if(i==input.back()){
// cout<<i<<endl;
// }
// else cout<<i<<",";
//}
}
References:⚓︎
Last update:
January 17, 2023 02:11:57
Created: November 7, 2022 23:10:40
Created: November 7, 2022 23:10:40