Quick Sort

Quick sort is a divide-and-conquer algorithm that picks a pivot element and partitions the array around the pivot, placing smaller elements before it and larger elements after it.

Algorithm

The quick sort algorithm follows these steps:

1. Pick a pivot element from the array
2. Partition the array: elements less than pivot go left, elements greater go right
3. Recursively apply quick sort to the left and right partitions

Time Complexity

• Best case: $O(n\log n)$
• Average case: $O(n\log n)$
• Worst case: $O(n^2)$ (when pivot is always the smallest or largest element)

Implementation

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        # Choose a pivot element
        pivot = arr[len(arr) // 2]
        # Partitioning step
        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]
        # Recursively apply quick_sort to the partitions
        return quick_sort(left) + middle + quick_sort(right)

# Example usage with different numbers
arr = [45, 23, 78, 12, 56, 89, 34]
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)

Trace it by hand