Quicksort is a divide and conquer algorithm which relies on a partition operation: to partition an array an element called a **pivot** is selected. All elements smaller than the pivot are moved before it and all greater elements are moved after it. This can be done efficiently in linear time and in-place. The lesser and greater sublists are then recursively sorted.

Efficient implementations of quicksort (with in-place partitioning) are typically unstable sorts and somewhat complex but are among the fastest sorting algorithms in practice. Together with its modest **O(log n)** space usage, quicksort is one of the most popular sorting algorithms and is available in many standard programming libraries.

The most complex issue in quicksort is choosing a good pivot element; consistently poor choices of pivots can result in drastically slower O(n²) performance, if at each step the median is chosen as the pivot then the algorithm works in **O(n log n)**. Finding the median, however, is an O(n) operation on unsorted lists and therefore exacts its own penalty for sorting.

**Steps of Quicksort:**

As we saw the quicksort uses divide and conquer techniques, let’s see what actually is that:

**Divide:** Rearrange the elements and split the array into two subarrays and an element in between such that so that each element in the left subarray is less than or equal the middle element and each element in the right subarray is greater than the middle element.

**Conquer:** Recursively sort the two subarrays.

**Example:**

If you didn’t understand the above example then you check following animated representation explains how to find the pivot value in an array.

Let’s see the below example of **Quicksort partition():**

**arr[] =**{10, 80, 30, 90, 40, 50, 70}

Indexes: 0 1 2 3 4 5 6

low = 0, high = 6,

**pivot**= arr[h] = 70

Initialize index of smaller element,

**i=-1**

Traverse elements from j = low to high-1

**j = 0:** Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])

**i = 0**

arr[] = {**10**, 80, 30, 90, 40, 50, 70} // No change as i and j

// are same

**j = 1:** Since arr[j] > pivot, do nothing

// No change in i and arr[]

**j = 2:** Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])

**i = 1**

arr[] = {10, **30, 80**, 90, 40, 50, 70} // We swap 80 and 30

**j = 3:** Since arr[j] > pivot, do nothing

// No change in i and arr[]

**j = 4:** Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])

**i = 2**

arr[] = {10, 30, **40,** 90, **80,** 50, 70} // 80 and 40 Swapped

**j = 5 :** Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j]

**i = 3**

arr[] = {10, 30, 40, **50,** 80, **90,** 70} // 90 and 50 Swapped

We come out of loop because j is now equal to high-1.

Finally we place pivot at correct position by swapping arr[i+1] and arr[high] (or pivot)

arr[] = {**10, 30, 40, 50, 70, 90, 80**} // 80 and 70 Swapped

Now 70 is at its correct place. All elements smaller than 70 are before it and all elements greater than 70 are after it.

**Algorithm:**

Quicksort again uses the technique of divide-and-conquer. We proceed as follows:

- Pick an arbitrary element of the array (the pivot).
- Divide the array into two sub arrays, those that are smaller and those that are greater (the partition phase).
- Recursively sort the sub arrays.
- Put the pivot in the middle, between the two sorted sub arrays to obtain the final sorted array.

It is also known as partition exchange sort. It was **invented by** **CAR Hoare**. It is based on **partition(A, left, right)**. The basic concept of quicksort process is picking one element from an array and rearranges the remaining elements around it. This element divides the main list into two sublists. This chosen element is called a pivot. Once pivot is chosen, then it shifts all the elements less than pivot to the left of value pivot and all the elements greater than pivot are shifted to the right side. This procedure of choosing pivot and partition the list is applied recursively until sub-lists consisting of only one element.

**partition( A, left, right)** rearranges A[left..right] and finds and returns an integer q, such that A[left], …, A[q–1] <∼ pivot, A[q] = pivot, A[q+1], …, A[right] > pivot, where pivot is the middle element of a[left..right], before partitioning. (To choose the pivot element differently, simply modify the assignment to m).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
//quicksort partition Integer partition( T[] A, Integer left, Integer right) m = [left + right] / 2; swap( A[left], A[m]); pivot = A[left]; low = left + 1; high = right; //low = low value while ( low ≤ high ) //high = high value while ( A[hi] > pivot ) high = high – 1; while ( low ≤ high and A[low] < pivot ) low = low + 1; if ( low ≤ high ) swap( A[low], A[high]); low = low + 1; high = high – 1; swap( A[left], A[high]); return high |

**quicksort( A, left, right)** sorts A[left.. right] by using partition() to partition A[left.. right], and then calling itself recursively twice to sort the two subarrays.

1 2 3 4 5 |
void quicksort( T[] A, Integer left, Integer right) if ( left < right ) q = partition( A, left, right); quicksort( A, left, q–1); quicksort( A, q+1, right); |

The only difference between quick sort and randomized quick sort is, here we are generating 10 random array elements using **random()** function and sort that array elements using quick sort method.

## C++

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 |
#include<iostream> #include<stdlib.h> #include<time.h> using namespace std; ///program to perform randomized quick sort //lhs means (left hand side) and rhs means (right hand side) void swap(int *lhs, int *rhs) { if(lhs == rhs) { return; } int tmp = *lhs; *lhs = *rhs; *rhs = tmp; } int partition(int ar[],int len) { int i, pvt = 0; //swap random slot selection to end //arr[len - 1] will hold the pivot value. swap(ar + (rand() % len), ar + (len - 1)); for(i = 0; i < len; ++i) { if(ar[i] < ar[len - 1]) { swap(ar + i, ar + pvt++); } } //swap the pivot value into position swap(ar + pvt, ar +(len - 1)); return pvt; } void quicksort(int ar[],int len) { if(len < 2) { return; } int pvt = partition(ar,len); //note increment skips pivot slot quicksort(ar,pvt++); quicksort(ar + pvt,len - pvt); } // Driver function int main() { srand((unsigned int) time(NULL)); const int N = 10; int data[N],i; cout<<"Array before sorting:\n"; for(i = 0; i < N; ++i) { data[i] = rand() % 50 + 1; cout<<data[i]; cout<<" "; } quicksort(data,N); cout<<"\nAfter sorting:\n"; for(i = 0; i < N; ++i) { cout<<data[i]; cout<<" "; } //exit status return 0; } |

When you run the program, the output will be following:

1 2 3 4 5 |
Array before sorting: 11 39 25 45 3 44 33 22 1 11 After sorting: 1 3 11 11 22 25 33 39 44 45 |

**Advantages:**

- This is faster sorting method among all.
- Its efficiency is also relatively good.
- It requires a relatively small amount of memory

**Disadvantages:**

- It is a complex method of sorting so, it is little hard to implement than other sorting methods

**Time Complexity:**

- Best case: O (n log n)
- Average case: O (n log n)
- Worst case: O (n2 )