The time complexity of Quicksort is O(n log n) in the best case, O(n log n) in the average case, and O(n^2) in the worst case. But because it has the best performance in the average case for most inputs, Quicksort is generally considered the ?fastest? sorting algorithm. At the end of the day though, whatever the best sorting algorithm really is depends on the input (and who you ask).
How Quicksort Works
Quicksort (especially in-place Quicksort) can be a bit confusing, so let?s walk through an example to show how this sorting algorithm works.
Suppose we are given the following array to sort:
Now let?s choose something called a ?pivot point?. The goal is to rearrange the array such that all all elements less than the pivot are to its left, and all elements greater than the pivot are to its right. The choice of the pivot point is arbitrary; it can be the first element of the array, the last element of the array, or even a random element! For our purposes though, let?s choose the pivot point to be the last element in the array, 5.
After rearranging the array around the pivot point 5, we should obtain the following array:
We then recursively follow the above procedure for the subarrays to the left and to the right of the pivot point.
The subarray to the left of the pivot point is just one element. No point in sorting an array of length one, so there?s nothing to do here!
The left subarray
On the other hand, the subarray to the right of the pivot point is not so trivial. Following the procedure described above, let us choose 7 to be the new pivot point for this subarray.
The right subarray
After rearranging the elements of the subarray around the pivot point, we obtain the following:
The right subarray rearranged around the new pivot point, 7
By continuing recursively, and merging the left subarray with the pivot and the right subarray, a sorted array is returned.
The final sorted array: Quicksort(left subarray) + pivot + Quicksort(right subarray)
Implementation
Below is a full implementation of Quicksort in C++, including all supplementary functions as well as a test case.
Thanks for reading! If you find an error in this post, please feel free to comment below and I will do my best to address any issues.
