Quicksort is one of the most efficient sorting algorithms and is based on the divide-and-conquer approach. It was developed by Tony Hoare in 1959 and is still commonly used today.
In this comprehensive guide, we will cover the following:
Table of Contents
Open Table of Contents
Overview of Quicksort
Quicksort is based on the divide-and-conquer approach for sorting an array. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This continues until the base case of empty or single-element arrays is reached, which are inherently sorted.
The steps for quicksort are:
- Select the pivot element
- Partition the array into two sub-arrays based on the pivot
- Recursively sort the sub-arrays
Some key properties of quicksort:
- Extremely efficient on average - O(n log n) time complexity
- In-place sorting algorithm - only requires constant O(1) space
- Unstable sorting algorithm - doesn’t preserve order of equal elements
- Efficient for large data sets and complex sorts
- Can be slower than other sorts for small arrays
- Performance depends heavily on pivot selection
These characteristics make quicksort very fast for a variety of applications from sorting user data to complex machine learning algorithms.
Implementing Quicksort in Python
Let’s now go through a step-by-step implementation of the quicksort algorithm in Python.
1. Select the Pivot Element
There are different ways to choose the pivot:
- Always pick first, last, or random element
- Pick median of three random elements
- Pick median of first, middle and last elements
For simplicity, we will start with always picking the last element as the pivot:
def quicksort(arr):
# always use last element as pivot
pivot = arr[len(arr) - 1]
2. Partition the Array
This involves iterating through the array and swapping elements such that those less than the pivot are placed before elements greater than the pivot.
We will use a pointer i that increments left to right, while swapping elements less than the pivot to the front of the array.
def quicksort(arr):
pivot = arr[len(arr) - 1]
i = 0
for j in range(len(arr) - 1):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[len(arr)-1] = arr[len(arr)-1], arr[i]
The final swap places the pivot element between the two partitions.
3. Recursively Sort Sub-arrays
We simply call quicksort recursively on the slices from 0 to i-1 (left partition) and i+1 to the end (right partition).
def quicksort(arr):
# pivot selection and partition
quicksort(arr[0:i])
quicksort(arr[i+1:len(arr)])
Putting it all together, the full quicksort implementation is:
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) - 1]
i = 0
for j in range(len(arr)-1):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[len(arr)-1] = arr[len(arr)-1], arr[i]
quicksort(arr[0:i])
quicksort(arr[i+1:len(arr)])
return arr
We added a base case to handle empty or single-element arrays to avoid infinite recursion.
Let’s test it on an example array:
arr = [4, 2, 7, 3, 1, 6]
print(quicksort(arr))
# Output: [1, 2, 3, 4, 6, 7]
It correctly sorts the sample array!
Pivot Selection and Partitioning
Choosing the final element as pivot is simple but not optimal. Better alternatives include:
Median of Three Method
Pick median of first, middle and last elements as pivot:
def quicksort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
if arr[0] < arr[mid]:
if arr[mid] < arr[len(arr)-1]:
pivot = arr[mid]
else:
pivot = arr[0]
else:
if arr[len(arr)-1] < arr[mid]:
pivot = arr[mid]
else:
pivot = arr[len(arr)-1]
This reduces the chance of imbalanced partitions.
Random Pivot
Select a random index between 0 and length-1 as the pivot:
import random
# inside quicksort()
pivot_idx = random.randint(0, len(arr)-1)
pivot = arr[pivot_idx]
Randomness improves performance on already sorted or reversed arrays.
For partitioning, instead of swapping, we can keep track of the boundary point and only swap once. This reduces expensive swap operations.
def partition(arr, pivot):
i = 0
for j in range(len(arr)):
if arr[j] < pivot:
arr[j], arr[i] = arr[i], arr[j]
i += 1
arr[i], arr[len(arr)-1] = arr[len(arr)-1], arr[i]
return i
Careful pivot selection and partitioning improves efficiency and avoids worst-case O(n^2) performance.
Time and Space Complexity Analysis
Time Complexity
- Best case: O(n log n) - pivot divides array into equal halves
- Average case: O(n log n)
- Worst case: O(n^2) - already sorted, or bad pivot selection
Quicksort is very efficient on average. But worst-case occurs with poor pivots.
Space complexity
Quicksort sorts in-place requiring only O(log n) space for recursion stack.
Optimizations and Improvements
Some optimizations to further improve quicksort:
- Use insertion sort for smaller arrays
- Switch to heapsort if recursion depth exceeds limit
- Track duplicates and equal elements
- Parallelize using multi-threading
- Use 3-way partitioning scheme
These optimizations make quicksort faster and more robust in different scenarios.
Comparison with Other Sorts
Merge Sort
- O(n log n) average and worst-case
- Stable sort
- O(n) extra space complexity
Merge has better worst-case but requires more space. Useful if stability is needed.
Heap Sort
- O(n log n) time
- Space O(1)
- Slower than quicksort in practice
Good alternative if quicksort’s worst-case is unacceptable.
Intro Sort
- Quicksort + fallback to heapsort
- Good hybrid algorithm
Introsort combines advantages of both quicksort and heapsort.
So quicksort is preferred in most cases, but alternatives have tradeoffs to consider.
Usage Examples and Applications
Quicksort is extensively used due to its excellent performance:
- Sorting small and large arrays/lists
- Ordering machine learning datasets
- Sorting user data in applications
- Graph algorithms like finding strongly connected components
- Database systems
- CPU cache optimizations
It’s one of the most popular sorting algorithms used in practice across domains.
Exercises
Some practice questions to test your quicksort skills:
-
Implement quicksort with a random pivot and hoare partitioning scheme.
-
Track the number of comparisons and swaps your quicksort algorithm makes.
-
Modify quicksort to detect and handle duplicate elements.
-
Combine quicksort with insertion sort to create a hybrid algorithm.
-
Implement 3-way quicksort partitioning.
Conclusion
In this comprehensive guide, we implemented quicksort in Python from scratch, discussed key concepts like pivot selection and partitioning schemes, analyzed complexity, compared tradeoffs with other sorts, saw real-world applications, and worked through examples.
Quicksort is one of the fastest sorting algorithms due to its excellent divide-and-conquer approach. With some careful optimizations, it can be made even faster and adaptable for all kinds of sorting problems. Understanding quicksort provides a solid foundation in algorithmic thinking that is applicable across technical domains.
The implementation techniques, analysis, optimizations and examples covered in this guide will help prepare you for technical interviews. Quicksort remains a popular interview topic and being thorough with its concepts will give you an edge.
There are always opportunities to enhance the quicksort algorithm further through multi-threading, cache optimizations, hybrid schemes and more. I hope this guide provided a comprehensive overview and starting point for mastering quicksort in Python.