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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | 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 i |
Quicksort C implementation using different Pivoting Techniques
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | #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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | #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
