Given an array of integers, sort it using quicksort algorithm.

Quicksort is an efficient in-place sorting algorithm, which usually performs about two to three times faster than merge sort and heapsort when implemented well. Quicksort is a comparison sort, meaning that it can sort items of any type for which a *less-than* relation is defined. In efficient implementations, it is usually not a stable sort.

Quicksort on average takes O(nlog(n)) comparisons to sort n items. In the worst case, it makes O(n^{2}) comparisons, though this behavior is very rare.

## How Quicksort works?

Quicksort is a divide and conquer algorithm. Like all divide and conquer algorithms, quicksort first divides a large array into two smaller sub-arrays and then recursively sort the sub-arrays. Basically, three steps are involved in whole process –

**Pivot selection:***Pick an element, called a pivot, from the array (usually the leftmost or the rightmost element of the partition).*

**Partitioning:***Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning,**the pivot is in its final position.*

**Recurse:***Recursively apply the above steps to the sub-array of elements with smaller values than pivot and separately to the sub-array of elements with greater values than pivot.*

The base case of the recursion is arrays of size 1, which never need to be sorted.

Below diagram shows how at each step of the quicksort algorithm we choose leftmost element as pivot, parition the array across pivot and recuse on two sub-arrays we get after partition process.

Please note that the pivot selection and partitioning steps can be done in several different ways and the choice of specific implementation schemes greatly affects the algorithm’s performance. We will discuss all that in detail later, but let’s now get to the coding part.

Below is C++ implementation of quicksort algorithm –

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 |
#include <iostream> #include <algorithm> using namespace std; // Partition using Lomuto partition scheme int Partition(int a[], int start, int end) { // Pick rightmost element as pivot from the array int pivot = a[end]; // elements less than pivot will be pushed to the left of pIndex // elements more than pivot will be pushed to the right of pIndex // equal elements can go either way int pIndex = start; // each time we finds an element less than or equal to pivot, pIndex // is incremented and that element would be placed before the pivot. for (int i = start; i < end; i++) { if (a[i] <= pivot) { swap(a[i], a[pIndex]); pIndex++; } } // swap pIndex with Pivot swap (a[pIndex], a[end]); // return pIndex (index of pivot element) return pIndex; } // Quicksort routine void QuickSort(int a[] ,int start, int end) { // base condition if (start >= end) return; // rearrange the elements across pivot int pivot = Partition(a, start, end); // recurse on sub-array containing elements that are less than pivot QuickSort(a, start, pivot - 1); // recurse on sub-array containing elements that are more than pivot QuickSort(a, pivot + 1, end); } // Quicksort algorithm implementation in C++ int main() { int a[] = { 9, -3, 5, 2, 6, 8, -6, 1, 3 }; int n = sizeof(a)/sizeof(a[0]); QuickSort(a, 0, n - 1); // print the sorted array for (int i = 0 ; i < n; i++) cout << a[i] << " "; return 0; } |

`Output:`

-6 -3 1 2 3 5 6 8 9

## Quicksort Performance:

The worst case time complexity of Quicksort is O(n^{2}). The worst case happens when the pivot happens to be the smallest or largest element in the list, or when all the elements of array are equal. This will result in most unbalanced partition as the pivot divides the array into two sub-array of sizes 0 and n – 1. If this happens repeatedly in every partition (example, we have sorted array), then each recursive call processes a list of size one less than the previous list and that will result in O(n²) time.

T(n) = T(n-1) + cn = O(n²)

*(Note – partition takes O(n) time that accounts for cn)*

The best case time complexity of quicksort is O(nlog(n)). The best case happens when the pivot divides the array into two nearly equal pieces. Now each recursive call processes a list of half the size.

T(n) = 2 T(n/2) + cn = O(n log(n))

**Must Read:** How to Boost Quicksort performance?

**References:** https://en.wikipedia.org/wiki/Quicksort

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply