Quicksort is a highly efficient sorting algorithm, but from a Big-O perspective can look deceivingly slow. The algorithm works by splitting an array in two around a "pivot" point, with elements larger in one half, and elements smaller in another.

Assumptions

What is Quicksort?

Quicksort is a divide and conquer sorting algorithm that partitions an array into two parts based on a selected pivot, where the parts are less than or equal to, and greater than the pivot element respectively. > Natively, Quicksort is not stable or in place, though it is possible to implement them as both with extra logic.

Picking The Pivot

Because of how the elements are sorted into the partitions, it is desirable to pick a number that is close to the median of the elements in an array in order to have evenly-divided partitions. If we assume the array is randomized, there are a few approaches that are commonly used:

  1. Picking the first or last element (most common)
  2. Picking the median of the first, middle, and last element (most balanced)
  3. Picking a random element

> Below, we'll pick the last element for the partition pivot. 

 /* pseudo-code */
 function quicksort( int[] arr, int low, int high ) {
   if ( low < high ) {
     // Partition the array.
     int partition = partition(arr, low, high);
     // Now sort the left half of the array.
     quicksort( arr, low, partition - 1 );
     // And sort the right half of the array.
     quicksort( arr, partition + 1, high );
     // Notice that we don't include the partition element?
   }
 }

 // Partition function
 function partition( int[] arr, int low, int high ) {
   // Get the pivot element.
   int pivot = arr[high];
   int i = low;
   // Iterate over all other elements.
   for ( int j = low; j < high; j++ ) {
     // If arr[j] is less than the pivot..
     if ( arr[j] < pivot ) {
       // ..Swap i and j..
       swap( arr, i, j );
       // .. Increment i.
       i++; 
     }
   }
   // Finally, swap i and our pivot element (high).
   swap( arr, i, high );
   // Return the index of our i element (the pivot).
   return i;
   
 }

 // helper function to swap elements.
 function swap( int[] arr, int a, int b ) {
   int tmp = arr[a];
   arr[a]  = arr[b];
   arr[b] = tmp;
 }

Analysis of Quicksort

Worst Average Memory
O(n<sup>2</sup>) O(n log n) O(n)

Recalling <a href="https://www.devmaking.com/learn/algorithms/master-theorem/" target="_blank" style="color:inherit;">The Master Theorem</a>:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">T(n) = aT( n/b ) + O(n<sup>d</sup>)</div> Taking Quicksort step by step:

  • Partition the array into two parts. b = 2.
  • Perform Quicksort on the left half, then the right half. a = 2.
  • In each partition, iterate over the half of the array. O(n), d = 1.

Representing this by the master theorem results in T(n) = 2T(n/2) + O(n).

When we plug these numbers into the equation:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">d ? log<sub>b</sub>a is 1 = log<sub>2</sub>2</div><br> Therefore, we know that the resulting formula is:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">n<sup>d</sup>log<sub>b</sub>n = n<sup>1</sup>log<sub>2</sub>n</div> Which evaluates to a final result of

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">O(n log n)&#8718;</div> <br>

> Quicksort, like Merge Sort, is an optimal sorting algorithm, and in practice often works more efficiently than Merge Sort!

Worst-case Quicksort

While in ideal situations the partitions will always be of equal length, it is never guaranteed. The worst case scenario occurs when The partition is the lowest or highest element of the array. When this happens, one of the partitions will contain 0 elements, while the rest will contain n - 1 elements. This results in a worst-case runtime of O(n<sup>2</sup>).

> While it is very unlikely to occur, it most frequently happens when attempting to sort an already sorted array using the high or low pivot method.

Quicksort Walkthrough

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_QuickSort_01.png" alt="unsorted array" style="max-width:95%;"> </div>

Starting with the array, we partition. For this example, we'll partition around the last element; all elements greater than 5 will go after it, and all elements less than 5 will go before it.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_QuickSort_02.png" alt="array with the first pivot sorted." style="max-width:95%;"> </div>

Now, we'll do the same with the elements in the right and left partitions, using their last respective elements as pivots.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_QuickSort_03.png" alt="array with 3 pivots sorted" style="max-width:95%;"> </div>

This process of picking the last element of each sub array will continue until all elements are partitioned and the array is sorted.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_QuickSort_04.png" alt="array with many pivots sorted" style="\max-width:95%;"> </div>

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_QuickSort_05.png" alt="mostly sorted array" style="max-width:95%;"> </div>

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_QuickSort_06.png" alt="fully-sorted array" style="max-width:95%;"> </div>

Quicksort in Practice

Comparing this algorithm's runtime analysis to Merge Sort might raise the question as to why this should be used at all, when Merge Sort has a worst case equal to Quicksort's best case. The truth is, Quicksort (on average) performs better than Merge Sort; the main discrepancy comes as a result of Big-O notation generalizing the performance of algorithms. While Big-O is still a useful tool, Quicksort is one of the cases where it can be misleading to make an algorithm seem slower than it really is.

Further Resources