QuickSort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
The steps are:
On average, the algorithm takes O(n\log {n}) comparisons to sort n items. In the worst case, it makes O(n^{2}) comparisons.
Generally, the first item or the element is assumed to be the initial pivot element. Some choose the middle element and even the last element. It doesn’t fix the pivot element in the correct position.
// Sorts a (portion of an) array, divides it into partitions, then sorts those
algorithm quicksort(A, lo, hi) is
if lo >= 0 && hi >= 0 && lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p) // Note: the pivot is now included
quicksort(A, p + 1, hi)
// Divides array into two partitions
algorithm partition(A, lo, hi) is
// Pivot value
pivot := A[ floor((hi + lo) / 2) ] // The value in the middle of the array
// Left index
i := lo - 1
// Right index
j := hi + 1
loop forever
// Move the left index to the right at least once and while the element at
// the left index is less than the pivot
do i := i + 1 while A[i] < pivot
// Move the right index to the left at least once and while the element at
// the right index is greater than the pivot
do j := j - 1 while A[j] > pivot
// If the indices crossed, return
if i ≥ j then return j
// Swap the elements at the left and right indices
swap A[i] with A[j]C++ implementation of QuickSort using Hoare’s partition scheme:
#include <bits/stdc++.h>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot = arr[low];
int i = low - 1, j = high + 1;
while (true) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j) return j;
swap(arr[i], arr[j]);
}
}
void quicksort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quicksort(arr, low, pi);
quicksort(arr, pi + 1, high);
}
}In most formulations this scheme chooses as the pivot the last element in the array. This scheme degrades to O(n2) when the array is already in order. It fixes the pivot element in the correct position.
// Sorts a (portion of an) array, divides it into partitions, then sorts those
algorithm quicksort(A, lo, hi) is
// Ensure indices are in correct order
if lo >= hi || lo < 0 then
return
// Partition array and get the pivot index
p := partition(A, lo, hi)
// Sort the two partitions
quicksort(A, lo, p - 1) // Left side of pivot
quicksort(A, p + 1, hi) // Right side of pivot
// Divides array into two partitions
algorithm partition(A, lo, hi) is
pivot := A[hi] // Choose the last element as the pivot
// Temporary pivot index
i := lo - 1
for j := lo to hi - 1 do
// If the current element is less than or equal to the pivot
if A[j] <= pivot then
// Move the temporary pivot index forward
i := i + 1
// Swap the current element with the element at the temporary pivot index
swap A[i] with A[j]
// Move the pivot element to the correct pivot position (between the smaller and larger elements)
i := i + 1
swap A[i] with A[hi]
return i // the pivot indexC++ implementation QuickSort using Lomuto’s partition scheme:
#include <bits/stdc++.h>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
void quicksort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}
}