Basic Idea of Quick Sort¶

Quick Sort is an efficient sorting algorithm based on the “divide and conquer” principle. In simple terms, it first selects an element from the array as the “pivot,” then partitions the array into two parts: one with all elements smaller than the pivot and the other with all elements larger than the pivot. The algorithm then recursively applies Quick Sort to these two parts until the entire array is sorted.

Detailed Explanation of the Partition Process¶

Partitioning is the core step of Quick Sort. Let’s understand it with an example:

Suppose the array is [5, 3, 8, 4, 2, 7, 1, 6], and we select the first element 5 as the pivot. The partitioning process is as follows:

1. Initialize Pointers: left points to the left side of the array (initially 0, corresponding to element 5), and right points to the right side (initially 7, corresponding to element 6).
2. Move Pointers:
   - First, move the right pointer left until an element smaller than the pivot is found. Here, starting from index 7 (element 6), which is greater than 5, we move left to index 6 (element 1), which is smaller than 5, and stop.
   - Then, move the left pointer right until an element larger than the pivot is found. Starting from index 0 (element 5, the pivot), we move right to index 1 (element 3, smaller than 5) and continue to index 2 (element 8, larger than 5), then stop.
   - Swap Elements: Swap the elements at left (index 2) and right (index 6). The array becomes [5, 3, 1, 4, 2, 7, 8, 6].
3. Repeat the Process: Continue moving the pointers until left >= right. Eventually, left and right will meet at the middle position (at this point, left = right = 4). Swap the pivot (at index 0) with the element at left, resulting in the partitioned array: [2, 3, 1, 4, 5, 7, 8, 6].

At this point, all elements to the left of the pivot 5 (i.e., [2, 3, 1, 4]) are smaller than 5, and all elements to the right (i.e., [7, 8, 6]) are larger than 5.

Python Code Implementation¶

Partition Function¶

The partition function determines the final position of the pivot and splits the array into left and right parts:

def partition(arr, low, high):
    pivot = arr[low]  # Select the first element as the pivot
    left = low        # Left pointer
    right = high      # Right pointer

    while left < right:
        # Move right pointer left until finding an element smaller than the pivot
        while left < right and arr[right] > pivot:
            right -= 1
        # Move left pointer right until finding an element larger than the pivot
        while left < right and arr[left] < pivot:
            left += 1
        # Swap elements at left and right pointers
        if left < right:
            arr[left], arr[right] = arr[right], arr[left]

    # Place the pivot in its final position (at left=right)
    arr[low], arr[left] = arr[left], arr[low]
    return left  # Return the pivot's index

Quick Sort Function¶

Recursively call the partition function to sort the left and right subarrays:

def quick_sort(arr, low, high):
    if low < high:  # Base case: stop when the subarray length is 1 or 0
        # Partition and get the pivot index
        pivot_index = partition(arr, low, high)
        # Recursively sort the left subarray (elements before the pivot)
        quick_sort(arr, low, pivot_index - 1)
        # Recursively sort the right subarray (elements after the pivot)
        quick_sort(arr, pivot_index + 1, high)

Test Code¶

# Test the quick sort implementation
arr = [5, 3, 8, 4, 2, 7, 1, 6]
n = len(arr)
quick_sort(arr, 0, n - 1)
print("Sorted array:", arr)  # Output: Sorted array: [1, 2, 3, 4, 5, 6, 7, 8]

Code Explanation¶

1. Pivot Selection: We choose the first element of the array as the pivot (this can also be randomized to avoid worst-case scenarios).
2. Partition Logic: Using two pointers (left and right), we traverse the array, swapping elements that do not meet the pivot condition. This ensures all elements to the left of the pivot are smaller, and all elements to the right are larger.
3. Recursion Termination: The recursion stops when low >= high (subarray length is 1 or 0), as these subarrays are already sorted.

Complexity Analysis¶

• Time Complexity:
• Average Case: O(n log n) (each partition splits the array into roughly equal parts, with log n recursion depth and n elements processed per level).
• Worst Case: O(n²) (occurs when the array is already sorted and the first element is always chosen as the pivot; this can be mitigated by randomizing the pivot selection).

Conclusion¶

Quick Sort efficiently sorts arrays using the “divide and conquer + recursion” approach. Its core is the partitioning process: selecting a pivot, adjusting elements, and recursively processing subarrays. It is one of the most widely used sorting algorithms in practice, and understanding its principles and implementation is crucial for mastering sorting algorithms.

By following the examples and code provided, you can understand the execution process of Quick Sort and experiment with pivot selection methods (e.g., random pivot) to optimize the algorithm.