Python Quicksort Algorithm Guide
Explore the quicksort algorithm in Python. Learn pivot selection, partitioning, and recursion in this interactive coding example.
How it Works
Quicksort is an extremely fast and widely used sorting algorithm. Like merge sort, it employs a divide-and-conquer approach. However, quicksort sorts the elements 'in-place', making it memory efficient.
The algorithm works by selecting a 'pivot' element from the list. It then partitions the other elements into two sub-arrays: those less than the pivot and those greater than the pivot. This process is recursively applied to the sub-arrays.
Although Quicksort has a worst-case complexity of O(n²), its average-case runtime is O(n log n), and it typically outperforms merge sort in practice due to lower cache misses and zero overhead of creating temporary arrays.
Source Code
A concise recursive Quick Sort script using list comprehensions for high readability.
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Test list
data = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original List:", data)
sorted_data = quicksort(data)
print("Sorted List: ", sorted_data)Original List: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted List: [1, 3, 4, 5, 6, 7, 12, 15]Real-world Applications
- System sorting routines where memory footprint must be kept at a minimum
- General-purpose sorting in standard language library frameworks
- Academic teaching of partition mechanics and recursive divide-and-conquer
Frequently Asked Questions
How can we avoid the worst-case complexity of O(n²) in Quicksort?
The worst-case occurs when the selected pivot is repeatedly the smallest or largest element. To mitigate this, developers use strategies like choosing a random pivot or the "median-of-three" values.
Is Quicksort stable?
No, standard Quicksort is unstable. During partitioning, elements are swapped across long ranges, which can alter the relative order of duplicate elements.