sorting_algorithms.py

from __future__ import annotations

from typing import List, Callable


def bubble_sort(items: List[int]) -> List[int]:
    arr = items.copy()
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, 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
    return arr


def insertion_sort(items: List[int]) -> List[int]:
    arr = items.copy()
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr


def merge_sort(items: List[int]) -> List[int]:
    arr = items.copy()

    def _merge(left: List[int], right: List[int]) -> List[int]:
        merged: List[int] = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged

    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return _merge(left, right)


def quick_sort(items: List[int]) -> List[int]:
    arr = items.copy()

    def _quick_sort(values: List[int]) -> List[int]:
        if len(values) <= 1:
            return values
        pivot = values[len(values) // 2]
        less = [x for x in values if x < pivot]
        equal = [x for x in values if x == pivot]
        greater = [x for x in values if x > pivot]
        return _quick_sort(less) + equal + _quick_sort(greater)

    return _quick_sort(arr)


def get_sorting_algorithms() -> List[tuple[str, Callable[[List[int]], List[int]]]]:
    return [
        ("Bubble Sort", bubble_sort),
        ("Insertion Sort", insertion_sort),
        ("Merge Sort", merge_sort),
        ("Quick Sort", quick_sort),
    ]