Quick Sort Python Cheatsheet

Quick Sort is a divide-and-conquer algorithm. It works by selecting a pivot, then partitioning the array so that elements less than the pivot go to the left, and elements greater go to the right. It recursively applies the same strategy to the sub-arrays.

Algorithm

1. pick a pivot
2. partition the array into [elements ≤ pivot], [pivot], and [elements > pivot]
3. recursively quicksort on left and right subarray
4. combine results

Python code (Not in-place)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]  # Choose 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
arr = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(arr))  # Output: [1, 1, 2, 3, 6, 8, 10]

Python code (in-place)

def quick_sort_inplace(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort_inplace(arr, low, pivot_index - 1)
        quick_sort_inplace(arr, pivot_index + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low
    for j in range(low, high):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[high] = arr[high], arr[i]
    return i

# Example usage
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_inplace(arr, 0, len(arr) - 1)
print(arr)  # Output: [1, 1, 2, 3, 6, 8, 10]

Time complexity: O(n log n)

Space complexity: O(n) for not in-place, O(log n) for in-place