int partition(vector<int>& arr, int low, int high) {
int pivot = arr[low];
int i= low;
int j= high;
while(i<j){
while (arr[i] <= pivot && i < high) {
i++;
}
while (arr[j] > pivot && j > low) {
j--;
}
if (i < j) {
swap(arr[i], arr[j]);
}
}
swap(arr[low], arr[j]);
return j;
}
void quickSort(vector<int>& arr, int low, int high) {
if(low < high){
int partitionIndex = partition(arr , low , high);
quickSort(arr, low, partitionIndex-1);
quickSort(arr, partitionIndex+1, high);
}
}
Quick Sort Analysis Table
| Type |
Complexity |
Explanation |
| Time (Best) |
O(n log n) |
Pivot divides array evenly |
| Time (Average) |
O(n log n) |
Typical case, good pivot splits |
| Time (Worst) |
O(n²) |
Poor pivot (e.g., sorted or reverse-sorted data with first-element pivot) |
| Space (Recursive) |
O(log n) (best), O(n) (worst) |
Stack space due to recursion, worst case for unbalanced partitions |
| Stable? |
No |
Equal elements can be swapped and lose their original order |
| Used in |
General-purpose sorting, in-memory arrays, fast sort needs |
|