Quicksort Algorithm#

Welcome to Day 26 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive deep into the Quicksort algorithm, one of the most efficient and widely used sorting algorithms in practice.

See it in motion: watch quicksort partition 100 values around animated pivots in our free interactive visualizer.

Introduction to Quicksort#

Quicksort is a divide-and-conquer algorithm that 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.

How Quicksort Works#

1. Choose a pivot element from the array.
2. Partition the array around the pivot, such that:
   • All elements less than the pivot are moved to its left.
   • All elements greater than the pivot are moved to its right.
3. Recursively apply steps 1-2 to the sub-array of elements with smaller values and the sub-array of elements with greater values.

Basic Implementation of Quicksort#

Here’s a basic implementation of the Quicksort algorithm:

 1def quicksort(arr):
 2    if len(arr) <= 1:
 3        return arr
 4    else:
 5        pivot = arr[len(arr) // 2]
 6        left = [x for x in arr if x < pivot]
 7        middle = [x for x in arr if x == pivot]
 8        right = [x for x in arr if x > pivot]
 9        return quicksort(left) + middle + quicksort(right)
10
11# Example usage
12arr = [3, 6, 8, 10, 1, 2, 1]
13sorted_arr = quicksort(arr)
14print(f"Sorted array: {sorted_arr}")

In-place Quicksort Implementation#

While the above implementation is easy to understand, it’s not the most efficient as it creates new lists. Here’s an in-place implementation:

 1def partition(arr, low, high):
 2    pivot = arr[high]
 3    i = low - 1
 4    for j in range(low, high):
 5        if arr[j] <= pivot:
 6            i += 1
 7            arr[i], arr[j] = arr[j], arr[i]
 8    arr[i + 1], arr[high] = arr[high], arr[i + 1]
 9    return i + 1
10
11def quicksort_inplace(arr, low, high):
12    if low < high:
13        pi = partition(arr, low, high)
14        quicksort_inplace(arr, low, pi - 1)
15        quicksort_inplace(arr, pi + 1, high)
16
17# Example usage
18arr = [3, 6, 8, 10, 1, 2, 1]
19quicksort_inplace(arr, 0, len(arr) - 1)
20print(f"Sorted array: {arr}")

Time Complexity#

• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n^2) - This occurs when the pivot is always the smallest or largest element.

Space Complexity#

• O(log n) - Due to the recursive calls on the call stack.

Optimizations for Quicksort#

1. Choosing the Pivot#

The choice of pivot can significantly affect the performance of Quicksort. Some common strategies include:

1. Choose the first element as pivot
2. Choose the last element as pivot
3. Choose the middle element as pivot
4. Choose a random element as pivot
5. Median-of-three (choose the median of the first, middle, and last elements)

Here’s an implementation using the median-of-three strategy:

 1def median_of_three(arr, low, high):
 2    mid = (low + high) // 2
 3    if arr[low] <= arr[mid] <= arr[high] or arr[high] <= arr[mid] <= arr[low]:
 4        return mid
 5    elif arr[mid] <= arr[low] <= arr[high] or arr[high] <= arr[low] <= arr[mid]:
 6        return low
 7    else:
 8        return high
 9
10def partition_median(arr, low, high):
11    pivot_index = median_of_three(arr, low, high)
12    arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
13    return partition(arr, low, high)
14
15def quicksort_optimized(arr, low, high):
16    if low < high:
17        pi = partition_median(arr, low, high)
18        quicksort_optimized(arr, low, pi - 1)
19        quicksort_optimized(arr, pi + 1, high)
20
21# Example usage
22arr = [3, 6, 8, 10, 1, 2, 1]
23quicksort_optimized(arr, 0, len(arr) - 1)
24print(f"Sorted array: {arr}")

2. Handling Small Subarrays#

For small subarrays, it’s often more efficient to use a simpler sorting algorithm like insertion sort:

 1def insertion_sort(arr, low, high):
 2    for i in range(low + 1, high + 1):
 3        key = arr[i]
 4        j = i - 1
 5        while j >= low and arr[j] > key:
 6            arr[j + 1] = arr[j]
 7            j -= 1
 8        arr[j + 1] = key
 9
10def quicksort_hybrid(arr, low, high):
11    while low < high:
12        if high - low + 1 < 10:
13            insertion_sort(arr, low, high)
14            break
15        else:
16            pi = partition_median(arr, low, high)
17            if pi - low < high - pi:
18                quicksort_hybrid(arr, low, pi - 1)
19                low = pi + 1
20            else:
21                quicksort_hybrid(arr, pi + 1, high)
22                high = pi - 1
23
24# Example usage
25arr = [3, 6, 8, 10, 1, 2, 1]
26quicksort_hybrid(arr, 0, len(arr) - 1)
27print(f"Sorted array: {arr}")

Advantages and Disadvantages of Quicksort#

Advantages:#

1. Efficient on average: O(n log n)
2. In-place sorting: Requires little additional memory
3. Cache-friendly: Good locality of reference

Disadvantages:#

1. Worst-case time complexity of O(n^2)
2. Not stable: Does not preserve the relative order of equal elements
3. Vulnerable to pathological data sets that can trigger worst-case behavior

Applications of Quicksort#

1. General-purpose sorting: Used in many standard library sort functions
2. Numerical computations: Efficiently sorting large datasets
3. Information retrieval: Sorting search results
4. Database systems: Indexing and sorting records

Exercise#

1. Implement a three-way partitioning Quicksort that handles duplicate elements efficiently.
2. Create a version of Quicksort that uses two pivots instead of one.
3. Implement an iterative version of Quicksort using a stack to manage the recursive calls.

Summary#

Today, we explored the Quicksort algorithm, one of the most efficient and widely used sorting algorithms. We implemented basic and optimized versions of Quicksort, discussed its time and space complexity, and looked at various optimization techniques.

Quicksort’s efficiency and adaptability make it a crucial algorithm to understand for any programmer. Its divide-and-conquer approach is a powerful paradigm that can be applied to many other problems.

Tomorrow, we’ll dive into another efficient sorting algorithm: Mergesort. We’ll compare it with Quicksort and explore its unique characteristics. Stay tuned!

Solution#

 1def quicksort_3way(arr, low=0, high=None):
 2    if high is None:
 3        high = len(arr) - 1
 4    if low >= high:
 5        return arr
 6    pivot = arr[low]
 7    lt, i, gt = low, low, high
 8    while i <= gt:
 9        if arr[i] < pivot:
10            arr[lt], arr[i] = arr[i], arr[lt]
11            lt += 1
12            i += 1
13        elif arr[i] > pivot:
14            arr[gt], arr[i] = arr[i], arr[gt]
15            gt -= 1  # do not advance i, the swapped-in value is unclassified
16        else:
17            i += 1
18    quicksort_3way(arr, low, lt - 1)
19    quicksort_3way(arr, gt + 1, high)
20    return arr
21
22# Example usage
23arr = [3, 6, 8, 10, 1, 2, 1, 3, 3, 6]
24quicksort_3way(arr)
25print(f"Sorted array: {arr}")