How to do Quick Sort in Python (With Code Example and Diagram)

Quick sort is one of the most efficient sorting algorithms, especially for large datasets. It uses the divide-and-conquer approach to break down the problem into smaller subproblems, making it fast and efficient. This post will explain how it works and test it with data in an example.

---

What is Quick Sort?

Quick sort is a divide-and-conquer sorting algorithm that selects a pivot element and divides the array into two sub-arrays: one with elements smaller than the pivot and one with elements greater than the pivot. These sub-arrays are then sorted recursively until the entire array is sorted.

Time Complexity:

• Best Case: O(n log n) – When the pivot divides the array evenly.
• Worst Case: O(n²) – When the pivot leads to highly unbalanced partitions (e.g., sorting an already sorted array).

---

Quick Sort Algorithm in Python

Here’s the Python implementation of quick sort:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]  # Middle element as pivot
        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 quick_sort(left) + middle + quick_sort(right)

# Example usage:
data = [12, 4, 5, 6, 7, 3, 1, 15]
sorted_data = quick_sort(data)
print("Sorted array:", sorted_data)

Output:

Sorted array: [1, 3, 4, 5, 6, 7, 12, 15]

---

Diagram Explanation of Quick Sort:

To better visualize the sorting process, let’s walk through the steps for sorting the array [12, 4, 5, 6, 7, 3, 1, 15].

Step 1: [12, 4, 5, 6, 7, 3, 1, 15]  (Original array)
        Pivot = 6
        
        Left: [4, 5, 3, 1]
        Pivot: [6]
        Right: [12, 7, 15]

Step 2: Recursively sort the left sub-array: [4, 5, 3, 1]
        Sorted Left: [1, 3, 4, 5]
        Pivot: [6]
        Right: [12, 7, 15]

Step 3: Recursively sort the right sub-array: [12, 7, 15]
        Sorted Left: [7]
        Pivot: [12]
        Right: [15]

Step 4: Merge everything:
        [1, 3, 4, 5, 6, 7, 12, 15]  (Final sorted array)

---

Types of Partitioning in Quick Sort

Quick sort is known for its flexibility in partitioning strategies, which can affect the algorithm’s efficiency. Let’s look at the three most common types of partitioning used in quick sort:

1. Lomuto Partition Scheme

• Steps:
  1. Pick the last element as the pivot.
  2. Traverse the array, moving smaller elements to the left of the pivot and larger ones to the right.
  3. Place the pivot at its correct position.
• Pros: Simple and easy to implement.
• Cons: Less efficient for large arrays since it always chooses the last element as the pivot.

Lomuto Partition Code:

def lomuto_partition(arr, low, high):
    pivot = arr[high]  # Choose the last element as the pivot
    i = low - 1  # Pointer for greater element

    # Traverse through all elements
    for j in range(low, high):
        # If the current element is smaller than or equal to the pivot
        if arr[j] <= pivot:
            i += 1  # Move pointer to the right
            arr[i], arr[j] = arr[j], arr[i]  # Swap elements

    # Place the pivot in the correct position
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort_lomuto(arr, low, high):
    if low < high:
        # Partition the array using Lomuto partition
        pi = lomuto_partition(arr, low, high)
        # Recursively sort elements before and after partition
        quick_sort_lomuto(arr, low, pi - 1)
        quick_sort_lomuto(arr, pi + 1, high)

# Example usage
arr = [12, 4, 5, 6, 7, 3, 1, 15]
quick_sort_lomuto(arr, 0, len(arr) - 1)
print("Sorted array using Lomuto partition:", arr)

Output:

Sorted array using Lomuto partition: [1, 3, 4, 5, 6, 7, 12, 15]

2. Hoare Partition Scheme

The Hoare partition scheme chooses the first element as the pivot and uses two pointers (starting from opposite ends) to rearrange the elements. It swaps elements until the two pointers meet, then partitions the array.

Hoare Partition Code

def hoare_partition(arr, low, high):
    pivot = arr[low]  # Choose the first element as the pivot
    i = low - 1
    j = high + 1

    while True:
        # Move i to the right until we find an element greater than or equal to the pivot
        i += 1
        while arr[i] < pivot:
            i += 1

        # Move j to the left until we find an element smaller than or equal to the pivot
        j -= 1
        while arr[j] > pivot:
            j -= 1

        # If two pointers meet, return the partition point
        if i >= j:
            return j

        # Swap elements at i and j
        arr[i], arr[j] = arr[j], arr[i]

def quick_sort_hoare(arr, low, high):
    if low < high:
        # Partition the array using Hoare partition
        pi = hoare_partition(arr, low, high)
        # Recursively sort elements before and after partition
        quick_sort_hoare(arr, low, pi)
        quick_sort_hoare(arr, pi + 1, high)

# Example usage
arr = [12, 4, 5, 6, 7, 3, 1, 15]
quick_sort_hoare(arr, 0, len(arr) - 1)
print("Sorted array using Hoare partition:", arr)

Output:

Sorted array using Hoare partition: [1, 3, 4, 5, 6, 7, 12, 15]

3. Median-of-Three Partition Scheme

In the Median-of-Three partition scheme, the pivot is chosen as the median of the first, middle, and last elements. This improves partitioning by avoiding worst-case scenarios when the array is already or nearly sorted.

Median-of-Three Partition Code:

def median_of_three(arr, low, high):
    mid = (low + high) // 2
    # Compare and swap to find the median value
    if arr[low] > arr[mid]:
        arr[low], arr[mid] = arr[mid], arr[low]
    if arr[low] > arr[high]:
        arr[low], arr[high] = arr[high], arr[low]
    if arr[mid] > arr[high]:
        arr[mid], arr[high] = arr[high], arr[mid]
    # Return the index of the median value
    return mid

def lomuto_partition_with_median(arr, low, high):
    # Get the median of three
    median_index = median_of_three(arr, low, high)
    # Swap the median with the last element to use Lomuto partition
    arr[median_index], arr[high] = arr[high], arr[median_index]
    return lomuto_partition(arr, low, high)

def quick_sort_median(arr, low, high):
    if low < high:
        # Partition the array using Lomuto partition with Median-of-Three pivot selection
        pi = lomuto_partition_with_median(arr, low, high)
        # Recursively sort elements before and after partition
        quick_sort_median(arr, low, pi - 1)
        quick_sort_median(arr, pi + 1, high)

# Example usage
arr = [12, 4, 5, 6, 7, 3, 1, 15]
quick_sort_median(arr, 0, len(arr) - 1)
print("Sorted array using Median-of-Three partition:", arr)

Output:

Sorted array using Median-of-Three partition: [1, 3, 4, 5, 6, 7, 12, 15]

---

Summary of Partitioning Methods:

1. Lomuto Partition:
   • Simple but inefficient in terms of swaps.
   • Best for small datasets or easy-to-implement cases.
2. Hoare Partition:
   • Fewer swaps, more efficient than Lomuto.
   • Slightly more complex to implement but better for large datasets.
3. Median-of-Three Partition:
   • Reduces the likelihood of worst-case O(n²) performance.
   • Good choice when sorting large or nearly sorted arrays.

Each partitioning method offers unique strengths and trade-offs, so you can select the one that fits your needs.

Limitations of Quick Sort

While quick sort is a highly efficient sorting algorithm, it comes with a few limitations:

• The worst-case time complexity of O(n²): This happens when the pivot results in unbalanced partitions, such as when the array is already sorted or reverse sorted.
• Recursive algorithm: Quick sort uses recursion, leading to stack overflow for large arrays unless optimizations are made (e.g., tail recursion or an iterative approach).
• Not stable: Quick sort does not guarantee that the relative order of equal elements will be preserved. If stability is needed, consider using merge sort.
• Choice of pivot affects performance: A poor pivot selection can significantly degrade performance. Using a median-of-three partitioning scheme helps improve pivot selection.

---

Conclusion

Quick sort is a powerful and efficient sorting algorithm for most cases, especially when combined with an effective partitioning method. In this post, we covered how to implement quick sort in Python, explained its partitioning strategies, and outlined the limitations you should know.

For most general purposes, quick sort is a great choice, but if stability or avoiding the worst-case scenario is critical, algorithms like merge sort might be better suited.

Congratulations on reading to the end of this tutorial!

For further reading on sorting algorithms in Python, go to the articles:

• How to do Insertion Sort in Python
• How to Do Bubble Sort in Python
• How to do Merge Sort in Python
• How to Do Selection Sort in Python
• How to do Counting Sort in Python
• How to Do Radix Sort in Python
• How to Do Bucket Sort in Python
• How to Do Heap Sort in Python
• How to Do Pigeonhole Sort in Python

Go to the online courses page on Python to learn more about Python for data science and machine learning.

Have fun and happy researching!