06 Sorting

Sorting

Time Complexity

Algorithm	Average	Worst
Bubble Sort	O(n2)	O(n2)
Insertion Sort	O(n2)	O(n2)
Quick Sort	O(n log2 n)	O(n2)
Merge Sort	O(n log2 n)	O(n log2 n)

Bubble Sort

• Time: O(n²)
• Space: O(1)

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break

Quick Sort

• Time: Average O(n log n), Worst O(n
• Space: O(log n)

def quick_sort(arr, low=None, high=None):
    if low == None or high == None:
        low = 0
        high = len(arr) - 1

    def partition(arr, low, high):
        pivot = arr[high]
        i = low - 1

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

    if low < high:
        pa = partition(arr, low, high)
        quick_sort(arr, low, pa-1)
        quick_sort(arr, pa+1, high)
    return arr

Alternative Quick Sort

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

    less, greater = [], []
    pivot = lst[0]
    for i in range(1, len(lst)):
        if lst[i] < pivot:
            less.append(lst[i])
        else:
            greater.append(lst[i])
    less = quick_sort(less)
    greater = quick_sort(greater)

    return less + [pivot] + greater

Insertion Sort

• Time: O(n²)
• Space: O(1)

def insert_sort(arr):
    for i in range(len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

Merge Sort

• Time: O(n log n)
• Space: O(n)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    return result + left[i:] + right[j:]

def merge_sort(arr):
    n = len(arr)
    if n < 2:
        return arr
    mid = n // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))