Quick Sort Algorithm in Python | Explained

Quick Sort is a popular sorting algorithm that follows a divide-and-conquer approach.

1. Choose a Pivot: Select one element of the array (in this code, the element at index low).
2. Partition: Arrange the array such that all elements less than or equal to the pivot lie to the pivot’s left, and those greater than the pivot lie to its right.
3. Recursively sort the subarrays on both sides of the pivot.

When implemented well, Quick Sort can be extremely efficient, often outperforming more stable algorithms like Merge Sort in practice, due to better cache performance. However, it does have a worst-case time complexity of O(n²) if the pivot selection is poor.

So let’s get started with the [Problem Link].

1. Understanding the Code

def partition(arr, low, high):
    pivot = arr[low]
    i = low
    j = high

    while i < j:
        while arr[i] <= pivot and i <= high - 1:
            i += 1

        while arr[j] > pivot and j >= low + 1:
            j -= 1

        if i < j:
            arr[i], arr[j] = arr[j], arr[i]

    arr[low], arr[j] = arr[j], arr[low]
    return j

How the partition function works:

1. Pivot Selection
   • The first element in the current segment (arr[low]) is chosen as the pivot.
2. Initialize Pointers
   • i starts from low.
   • j starts from high.
3. Iterate until i < j
   • Move i right as long as arr[i] <= pivot. This step stops when you find an element that is greater than the pivot.
   • Move j left as long as arr[j] > pivot. This step stops when you find an element that is less than or equal to the pivot.
4. Swap
   • If i < j, swap arr[i] and arr[j]. This pushes the large element (found at i) to the right part of the array and brings the smaller element (found at j) into the left part.
5. Final Pivot Swap
   • Once the while i < j loop ends, j effectively points to the position where the pivot should be placed.
   • Swap arr[low] and arr[j] so that the pivot moves to its correct sorted position.
   • Return j (the new index of the pivot) to the calling function.

By the end of partition, all elements to the left of arr[j] are less than or equal to the pivot, and all elements to the right of arr[j] are greater than the pivot.

def quick_sort(arr, low, high):
    if low < high:
        p_index = partition(arr, low, high)
        quick_sort(arr, low, p_index - 1)
        quick_sort(arr, p_index + 1, high)

How the quick_sort function works:

1. Base Condition:
   • If low >= high, it means the segment of the array is of size 0 or 1, which is already sorted.
2. Partition and Recursion:
   • Call partition(arr, low, high) to place the pivot in its correct position, and get that index as p_index.
   • Recursively sort the two subarrays:
     • Elements before the pivot: from low to p_index – 1.
     • Elements after the pivot: from p_index + 1 to high.

Also read about the Python Program to Implement Merge Sort Algorithm.

2. Example: Step-by-Step Dry Run

Given:

arr = [64, 34, 25, 12, 22, 12, 12, 11, 90]
quick_sort(arr, 0, len(arr) - 1)
print(f"Sorted array = {arr}")

Initial Call: quick_sort(arr, 0, 8) (since len(arr) – 1 = 8).

1. First Partition:
   • low = 0, high = 8, pivot = arr[0] = 64.
   • i = 0, j = 8.
   • Move i right until arr[i] is > pivot.
   • Move j left until arr[j] is ≤ pivot.
   • Swap elements when i < j.
   • Eventually, swap the pivot into its correct position, returning the index of the pivot.
   • After this partition, the pivot (64) sits in its final position, with all smaller or equal elements to its left and larger elements to its right.
2. Recursive Sort of Left and Right Segments:
   • Left side: everything before pivot index.
   • Right side: everything after pivot index.
   • Each segment is similarly partitioned and sorted.
3. Final Sorted Array:
   • After the recursion completes for all subparts, the entire list becomes sorted.

In practice, because there are repeated elements like 12 and 12, the code ensures they all end up in the correct final positions relative to 64 and 90.

3. Time Complexity

• Best and Average Case: O(nlog⁡n). When the pivot divides the array into subarrays of nearly equal size, you get more balanced splits.
• Worst Case: O(n²). If the pivot is consistently chosen poorly (for example, the smallest or largest element in each partition), each partition results in extremely unbalanced subarrays.

4. Space Complexity

• Quick Sort is generally considered an in-place sort since it rearranges the array in-place.
• Space complexity is O(log⁡n) for the recursion call stack in the best/average case. In the worst case, it can go up to O(n) because of the depth of the recursion tree.

5. Key Takeaways

1. Pivot Selection Matters: Different strategies for selecting the pivot (first element, last element, random pivot, median-of-three, etc.) can significantly influence performance.
2. In-Place Sort: Quick Sort does not need extra arrays (unlike Merge Sort), so memory usage can be lower in typical implementations.
3. Unstable: Quick Sort does not guarantee that identical elements remain in their original order.

Widely Used: Due to good average-case performance, it’s often the default choice in many standard libraries (e.g., C++ STL’s sort uses a variant of Quick Sort called introsort).

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.