Quick Sort Algorithm

Problem

Sort an array of elements efficiently using the Quick Sort algorithm, which uses a divide-and-conquer approach with a pivot element.

Solution

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    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
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sort(arr)
print(f"Original: {arr}")
print(f"Sorted: {sorted_arr}")

Time Complexity

• Time: O(n log n) average case, O(n²) worst case
• Space: O(log n) average case due to recursion stack

Key Points

1. Pivot Selection: Choose a pivot element (first, last, middle, or random)
2. Partitioning: Divide array into elements smaller and larger than pivot
3. Recursion: Recursively sort the sub-arrays
4. In-place: Can be implemented to sort in-place without extra space
5. Unstable: Relative order of equal elements may change

When to Use

• When you need average-case O(n log n) performance
• When in-place sorting is preferred
• When cache performance is important (good locality)
• When you need a simple, efficient sorting algorithm