Quicksort is a widely used sorting algorithm known for its efficiency and simplicity. Developed by Tony Hoare in 1960, this sorting technique follows the “divide and conquer” paradigm which makes it a powerful tool for organizing data in ascending or descending order. Programmers find quicksort to be an excellent introduction to sorting algorithms due to its straightforward implementation and elegant design.
The algorithm operates by selecting a “pivot” element from the array and partitioning the other elements into two sub-arrays, where elements less than the pivot are placed on one side, and elements greater than the pivot on the other. This process is then applied recursively to the sub-arrays until the entire array is sorted. Despite its simplicity, quicksort boasts impressive average-case time complexity. As you delve into quicksort, you’ll gain valuable insights into the divide-and-conquer approach widely employed in various problem-solving scenarios.
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)
Table of Contents
- What are the Steps to Perform Quick Sort?
- How to Pick Pivot Element?
- Quicksort Variants
- Quicksort Algorithm Complexity
- Pseudocode of Lomuto Partition
- Quicksort Implementation in C by using Different Pivoting Techniques
- Quicksort Implementation With Highlighted Steps
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.
- Block Quicksort – This algorithm performs partition by dividing the 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.
Quicksort Algorithm Complexity
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 Implementation in C by 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 Algorithm, Bubble Sort Implementation, Insertion Sort, Selection Sort
