Quick Sort

Quick Sort works by:

1. Choosing a Pivot: Selecting an element from the array to use as a reference.
2. Partitioning: Rearranging elements such that all elements smaller than the pivot come before it, and all elements greater than the pivot come after it.
3. Recursion: Recursively applying the same process to the left and right subarrays (elements before and after the pivot).

The efficiency of Quick Sort largely depends on the choice of the pivot. A poorly chosen pivot can lead to unbalanced partitions, resulting in the worst-case time complexity of O(n²).

Time Complexity:

• Average Case: O(n log n)
• Worst Case: O(n²) (when the pivot selection consistently results in highly unbalanced partitions, e.g., choosing the smallest or largest element in a sorted or nearly sorted array)
• Space Complexity: O(log n) for the recursive stack in the average case

Quick Sort Algorithm Steps

Choose a Pivot: Several strategies exist for choosing a pivot, including:

• First element (simple but may perform poorly on sorted data).
• Last element (similar issues as the first).
• Random element (helps reduce the chance of worst-case performance).
• Median of Three (choosing the median of the first, middle, and last elements).

Partitioning:

• Place the pivot in its correct sorted position.
• Move elements smaller than the pivot to the left and larger elements to the right.

Recursive Sorting:

• Recursively apply Quick Sort to the left and right subarrays around the pivot.

Example: Quick Sort with Partition Function

Here’s a Python implementation of Quick Sort with a partition helper function

from typing import List

def quick_sort(arr: List[int], low: int, high: int) -> None:
    """ 
    Perform quicksort on the array `arr` from index `low` to `high`.
    - arr: List of integers to sort
    - low: Starting index of the segment to sort
    - high: Ending index of the segment to sort
    """
    if low < high:
        # Partition the array and get the pivot index
        pivot_index = partition(arr, low, high)
        
        # Recursively apply quicksort to the left and right subarrays
        quick_sort(arr, low, pivot_index - 1)  # Sort elements before pivot
        quick_sort(arr, pivot_index + 1, high)  # Sort elements after pivot

def partition(arr: List[int], low: int, high: int) -> int:
    """ 
    Partition the array `arr` using the last element as the pivot.
    - arr: List of integers to partition
    - low: Starting index of the segment to partition
    - high: Ending index of the segment to partition
    Returns the index of the pivot after partitioning.
    """
    pivot = arr[high]  # Choose the pivot as the last element
    i = low - 1  # Place for swapping
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1  # Increment the smaller element index
            arr[i], arr[j] = arr[j], arr[i]  # Swap elements
    
    # Place the pivot element at its correct position
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1  # Return the pivot index

Explanation of Code

quick_sort Function:

• This function divides the array into two parts based on the partition function and recursively sorts each part.

1. It stops recursing when low >\= high, meaning the subarray has one or no elements.

partition Function:

• The partition function rearranges the array such that elements smaller than the pivot are on the left, and elements greater are on the right.
• The pivot is placed in its correct sorted position, and the function returns its index.

Example Usage:

arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)
# Output: Sorted array: [1, 5, 7, 8, 9, 10]

Common Mistakes

Incorrect Pivot Index:

• Make sure the pivot_index returned by partition is correctly used in recursive calls to avoid infinite recursion.
• Failing to partition correctly can cause elements to be in the wrong order.

Choosing a Poor Pivot:

• Using the first or last element as a pivot in a nearly sorted or reverse sorted array can lead to worst-case performance. Using a random pivot or median of three strategy often improves performance.

Recursive Stack Overflow:

• Quick Sort can cause a stack overflow on deep recursion with large arrays. Some implementations use tail call optimization or convert to an iterative approach for large arrays.

In-Place Requirement:

• Quick Sort is in-place, meaning it does not use extra space beyond the recursion stack. Ensure your implementation respects this by swapping elements directly in the array rather than creating additional arrays.

Handling Duplicates:

• For arrays with many duplicate elements, Quick Sort’s efficiency can drop. Consider using a three-way partitioning variant of Quick Sort for such cases.