Quicksort is a well-known sorting algorithm developed by C.A.R. Hoare: Quicksort. Quicksort is an efficient algorithm based on Divide and Conquer rule and is still a commonly used algorithm for sorting. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays and recursively sorting them.
Computer Journal, Vol. 5, 1, 10-15 (1962)
What are the steps to perform Quick Sort?
- Pick an element, called a pivot, from the array.
- Partition operation – reorder the array so that elements with values less than the pivot come left, and elements with values greater than the pivot come to the right of the pivot.
- Recursively apply the above two steps to the sub-arrays i.e. elements to the left and right of the pivot.
How to pick pivot element?
Pivot is picked up in four possible different ways.
- Pick first element as pivot which was used is earliest versions of Quick Sort.
- Pick last element as pivot also called Lomuto partition.
- Pick a random element as pivot.
- Pick median as pivot i.e. choosing the median of the first, middle and last element of the partition for the pivot. This is also called “median-of-three”.
Quicksort Variants
- Multi-pivot or multiquicksort quicksort – Partition the input variable number of pivots and subarrays.
- External quicksort – This is a kind of three-way quicksort in which the middle partition (buffer) represents a sorted subarray of elements.
- Three-way radix quicksort – This algorithm is a combination of radix sort and quicksort.
- Quick radix sort – This is again combination of radix sort and quicksort with some minor modifications.
- BlockQuicksort – This algorithm perofmrs partition by dividing th input into constant sized blocks.
- Partial and incremental quicksort – Only sorts limited number of smallest or largest elements i.e. top 10 elements. Look at std::partial_sort for details.
On average it makes O (n log n) (big O notation) comparisons to sort n items, but in the worst cases it is as slow as bubble sort i.e O(n2).
Pseudocode of Lomuto partition
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p - 1)
quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo
for j := lo to hi do
if A[j] < pivot then
swap A[i] with A[j]
i := i + 1
swap A[i] with A[hi]
return iQuicksort C implementation using different Pivoting Techniques
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
int partition_pivot_last(int array[], int low, int high) {
int pivot = array[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++i], &array[j]);
}
}
swap(&array[i + 1], &array[high]);
return (i + 1);
}
int partition_pivot_first(int array[], int low, int high) {
int pivot = array[low];
int i = (low + 1);
for (int j = low + 1; j <= high; j++) {
if (array[j] < pivot) {
if (j != i) {
swap(&array[i], &array[j]);
}
i++;
}
}
swap(&array[i - 1], &array[low]);
return (i - 1);
}
int partition_pivot_random(int array[], int low, int high) {
int pivot;
int n = rand();
pivot = low + n % (high - low + 1); // Randomizing the pivot
return partition_pivot_last(array, low, high);
}
int partition_pivot_median(int array[], int low, int high) {
int pivot;
int mid = (low + high) / 2;
if (array[mid] < array[low])
swap(&array[mid], &array[low]);
if (array[high] < array[low])
swap(&array[high], &array[low]);
if (array[high] < array[mid])
swap(&array[high], &array[mid]);
swap(&array[mid], &array[high-1]);
pivot = array[high-1];
return partition_pivot_last(array, low, high);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
//int pi = partition_pivot_first(array, low, high);
//int pi = partition_pivot_last(array, low, high);
//int pi = partition_pivot_random(array, low, high);
int pi = partition_pivot_median(array, low, high);
// Sort the elements on the left of pivot
quickSort(array, low, pi - 1);
// Sort the elements on the right of pivot
quickSort(array, pi + 1, high);
}
}
int main(void) {
int array[] = { 1, 3, 2, 4, 6, 8, 7, 9, 5 };
int size = sizeof(array) / sizeof(array[0]);
for (int i = 0; i < size; i++)
printf("|%d", array[i]);
printf("\n");
quickSort(array, 0, size - 1);
printf("\n");
for (int i = 0; i < size; i++)
printf("|%d", array[i]);
getchar();
return 0;
}Quicksort implementation with highlighted steps
The following implementation works in Visual Studio only as it uses text highlighting technique which is specific to Microsoft Windows only.
#include <stdio.h>
#include <stdlib.h>
//Visual studio specific to show colors etc.
#include <iostream>
#include <windows.h>
void printArray(int array[], int a, int b, int step, int div)
{
HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
if (step == 0)
printf("\n");
for (int i = 0; i <= 8; i++) {
if (a == array[i] || b == array[i]) {
SetConsoleTextAttribute(hConsole, FOREGROUND_RED);
printf("%d ", array[i]);
}
else {
SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE);
printf("%d ", array[i]);
}
}
SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE);
if (step == 99) {
printf(" ---> Step %d swap(%d, %d) Run: %d\n", step, a, b, div);
}
else {
printf(" ---> Step %d low:%d, high:%d Run: %d\n", step, a, b, div);
}
}
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
int partition_pivot_last(int array[], int low, int high, int div) {
int pivot = array[high];
int i = (low - 1);
int step = 0;
printArray(array, array[low], array[high], 0, div);
for (int j = low; j < high; j++) {
if (array[j] < pivot) {
swap(&array[++i], &array[j]);
printArray(array, array[i], array[j], ++step, div);
}
}
swap(&array[i + 1], &array[high]);
printArray(array, array[i + 1], array[high], 99, div);
return (i + 1);
}
int partition_pivot_first(int array[], int low, int high, int div) {
int pivot = array[low];
int i = (low + 1);
int step = 0;
printArray(array, array[low], array[high], 0, div);
for (int j = low + 1; j <= high; j++) {
if (array[j] < pivot) {
if (j != i) {
swap(&array[i], &array[j]);
printArray(array, array[i], array[j], ++step, div);
}
i++;
}
}
swap(&array[i - 1], &array[low]);
printArray(array, array[i - 1], array[low], 99, div);
return (i - 1);
}
int partition_pivot_random(int array[], int low, int high, int div) {
int pivot;
int n = rand();
pivot = low + n % (high - low + 1); // Randomizing the pivot
printArray(array, array[high], array[pivot], 0, div);
//swap(&array[high], &array[pivot]);
return partition_pivot_last(array, low, high, div);
}
int partition_pivot_median(int array[], int low, int high, int div) {
int pivot;
int mid = (low + high) / 2;
if (array[mid] < array[low])
swap(&array[mid], &array[low]);
if (array[high] < array[low])
swap(&array[high], &array[low]);
if (array[high] < array[mid])
swap(&array[high], &array[mid]);
swap(&array[mid], &array[high - 1]);
pivot = array[high - 1];
//swap(&array[pivot], &array[low]);
return partition_pivot_last(array, low, high, div);
}
void quickSort(int array[], int low, int high, int div) {
if (low < high) {
//int pi = partition_pivot_first(array, low, high, div);
//int pi = partition_pivot_last(array, low, high, div);
//int pi = partition_pivot_random(array, low, high, div);
int pi = partition_pivot_median(array, low, high, div);
div++;
// Sort the elements on the left of pivot
quickSort(array, low, pi - 1, div);
// Sort the elements on the right of pivot
quickSort(array, pi + 1, high, div);
}
}
int main(void) {
int array[] = { 1, 3, 2, 4, 6, 8, 7, 9, 5 };
int size = sizeof(array) / sizeof(array[0]);
for (int i = 0; i < size; i++)
printf("|%d", array[i]);
printf("\n");
quickSort(array, 0, size - 1, 0);
printf("\n");
for (int i = 0; i < size; i++)
printf("|%d", array[i]);
getchar();
return 0;
}
See also: Shell Sort, Bubble Sort, Insertion Sort, Selection Sort