Sorting Algorithms

"""Topic: Comparison of bubble sort & insertion sort
Time: O(n²) average/worst, O(n) best (if already sorted)
Space: O(1) — in-place"""

import random
import time


#── Bubble Sort ──────────────────────────────────────────────────────────────────────

def bubble_sort(arr: list[int]) -> tuple[list[int], int]:
    """Bubble sort.

    Compares two adjacent elements and sends the larger value back.
    Returns:
        (sorted array, number of exchanges)"""
    a = arr[:]
    n = len(a)
    swaps = 0
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swaps += 1
                swapped = True
        if not swapped:        #Early termination if already sorted
            break
    return a, swaps


#── Insertion sort ─────────────────────────────────────────────────────────────────────

def insertion_sort(arr: list[int]) -> tuple[list[int], int]:
    """Insertion sort.

    Inserts the current element into the sorted section at the appropriate position.
    Returns:
        (sorted array, number of moves)"""
    a = arr[:]
    n = len(a)
    moves = 0
    for i in range(1, n):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
            moves += 1
        a[j + 1] = key
    return a, moves


#── Step-by-step visualization ─────────────────────────────────────────────────────────────────

def bubble_sort_verbose(arr: list[int]) -> list[int]:
    """Array status output after each pass."""
    a = arr[:]
    n = len(a)
    print(f"initial: {a}")
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        print(f"pass{i + 1:2d}: {a}")
        if not swapped:
            print("↳ No exchange → Early termination")
            break
    return a


def insertion_sort_verbose(arr: list[int]) -> list[int]:
    """Output array status after each insertion."""
    a = arr[:]
    n = len(a)
    print(f"initial: {a}")
    for i in range(1, n):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
        print(f"Insert[{i}]: Insert {a} ← {key}")
    return a


#── Performance comparison ────────────────────────────────────────────────────────────────────

def compare_performance(n: int = 1000) -> None:
    """Comparison of execution time and number of operations of two sorts with random arrays."""
    data = [random.randint(0, 10000) for _ in range(n)]

    t0 = time.perf_counter()
    _, b_swaps = bubble_sort(data)
    t1 = time.perf_counter()
    _, i_moves = insertion_sort(data)
    t2 = time.perf_counter()

    print(f"\n=== n={n} Random array performance comparison ===")
    print(f"bubble sort: swap {b_swaps:>10,} times | {t1 - t0:.4f} seconds")
    print(f"Insertion sort: moves {i_moves:>10,} times | {t2 - t1:.4f} seconds")

    #almost sorted array
    nearly = list(range(n))
    for _ in range(max(1, n // 50)):    #2% random exchange
        i, j = random.sample(range(n), 2)
        nearly[i], nearly[j] = nearly[j], nearly[i]

    _, b_sw2 = bubble_sort(nearly)
    _, i_mv2 = insertion_sort(nearly)
    print(f"\n=== n={n} nearly sorted array ===")
    print(f"Bubble Sort: Swap {b_sw2:>10,} times")
    print(f"Insertion sort: Move {i_mv2:>10,} times ← Insertion sort is advantageous!")


#── Main ─────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    sample = [64, 34, 25, 12, 22, 11, 90]

    print("=" * 50)
    print("Bubble sort step-by-step visualization")
    print("=" * 50)
    bubble_sort_verbose(sample)

    print()
    print("=" * 50)
    print("Insertion sort step-by-step visualization")
    print("=" * 50)
    insertion_sort_verbose(sample)

    compare_performance(n=2000)

    #Accuracy Verification
    test = [random.randint(-100, 100) for _ in range(20)]
    b_result, _ = bubble_sort(test)
    i_result, _ = insertion_sort(test)
    expected = sorted(test)
    print(f"\nVerify accuracy: {'PASS' if b_result == i_result == expected else 'FAIL'}")

"""Topic: Merge Sort (Recursive & Iterative)
Time: O(n log n) — best/average/worst all
Space: O(n) — auxiliary array required"""

import random


#── Recursive merge sort ───────────────────────────────────────────────────────────────

_merge_count = 0     #Merge call count global counter


def merge(arr: list[int], left: int, mid: int, right: int) -> int:
    """Merge the two sorted intervals [left, mid], [mid+1, right].

    Returns:
        Number of comparisons performed in this merge"""
    global _merge_count
    _merge_count += 1

    left_sub = arr[left:mid + 1]
    right_sub = arr[mid + 1:right + 1]

    i = j = 0
    k = left
    comparisons = 0
    while i < len(left_sub) and j < len(right_sub):
        comparisons += 1
        if left_sub[i] <= right_sub[j]:
            arr[k] = left_sub[i]
            i += 1
        else:
            arr[k] = right_sub[j]
            j += 1
        k += 1

    while i < len(left_sub):
        arr[k] = left_sub[i]
        i += 1
        k += 1
    while j < len(right_sub):
        arr[k] = right_sub[j]
        j += 1
        k += 1

    return comparisons


def merge_sort_recursive(arr: list[int], left: int, right: int) -> None:
    """Recursive merge sort (in-place modification)."""
    if left >= right:
        return
    mid = (left + right) // 2
    merge_sort_recursive(arr, left, mid)
    merge_sort_recursive(arr, mid + 1, right)
    merge(arr, left, mid, right)


#── Iterative Merge Sort (Bottom-Up) ──────────────────────────────────────────────────

def merge_sort_iterative(arr: list[int]) -> list[int]:
    """Bottom-up iterative merge sort.

    Size 1 → 2 → 4 → 8... Merge in order.
    Operates without a recursive stack."""
    a = arr[:]
    n = len(a)
    size = 1
    while size < n:
        for left in range(0, n, size * 2):
            mid = min(left + size - 1, n - 1)
            right = min(left + size * 2 - 1, n - 1)
            if mid < right:
                merge(a, left, mid, right)
        size *= 2
    return a


#── Step visualization ─────────────────────────────────────────────────────────────────

def merge_sort_verbose(arr: list[int], depth: int = 0) -> list[int]:
    """Visualize the split/merge process with indentation."""
    indent = "  " * depth
    if len(arr) <= 1:
        print(f"{indent}└ {arr}")
        return arr[:]

    mid = len(arr) // 2
    print(f"{indent}split: {arr} → {arr[:mid]} | {arr[mid:]}")
    left = merge_sort_verbose(arr[:mid], depth + 1)
    right = merge_sort_verbose(arr[mid:], depth + 1)

    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:])

    print(f"{indent}Merge: {left} + {right} → {merged}")
    return merged


#── Main ─────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    #Step visualization (small scale)
    small = [5, 2, 8, 1, 9, 3]
    print("=" * 55)
    print("Merge Sort Split/Merge Visualization")
    print("=" * 55)
    result = merge_sort_verbose(small)
    print(f"\nFinal result: {result}")

    #recursive sort
    data = [random.randint(1, 100) for _ in range(16)]
    print(f"\nBefore recursive merge sort: {data}")
    _merge_count = 0
    arr_copy = data[:]
    merge_sort_recursive(arr_copy, 0, len(arr_copy) - 1)
    print(f"After recursive merge sort: {arr_copy}")
    print(f"Number of merge function calls: {_merge_count} times (n-1 = {len(data)-1})")

    #repeat sort
    arr2 = data[:]
    _merge_count = 0
    arr2_sorted = merge_sort_iterative(arr2)
    print(f"\nAfter repeated merge sorting: {arr2_sorted}")
    print(f"Number of merge function calls: {_merge_count} times")

    #Accuracy Verification
    assert arr_copy == arr2_sorted == sorted(data), "Alignment error!"
    print("\nAccuracy Verification: PASS")

    #Check stable alignment
    students = [("Alice", 85), ("Bob", 92), ("Charlie", 85), ("Dave", 92)]
    #Sort by score (stable: same scores maintain original order)
    students_sorted = sorted(students, key=lambda x: x[1])
    print(f"\nCheck stable sorting: {students_sorted}")
    print("← Same score (85: Alice<Charlie, 92: Bob<Dave) order maintained")

"""Topic: Quick Sort (Random Pivot)
Time: O(n log n) average, O(n²) worst (when pivot is always at min/max)
Space: O(log n) average (recursive stack), O(n) worst"""

import random
import sys

sys.setrecursionlimit(300_000)


#── Default quick sort (always pivot last element) ───────────────────────────────────────

def partition(arr: list[int], low: int, high: int) -> int:
    """Lomuto partition scheme.

    Set the pivot to high index,
    Send elements smaller than the pivot to the left."""
    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


def quick_sort_basic(arr: list[int], low: int, high: int) -> None:
    """Always use the last element as pivot (O(n²) in an already sorted array)."""
    if low < high:
        pi = partition(arr, low, high)
        quick_sort_basic(arr, low, pi - 1)
        quick_sort_basic(arr, pi + 1, high)


#── Random Pivot Quick Sort ──────────────────────────────────────────────────────────

def partition_random(arr: list[int], low: int, high: int) -> int:
    """Lomuto partition after exchanging random index and high."""
    rand_idx = random.randint(low, high)
    arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
    return partition(arr, low, high)


def quick_sort_random(arr: list[int], low: int, high: int) -> None:
    """Random pivot quicksort — probabilistically avoids the worst case."""
    if low < high:
        pi = partition_random(arr, low, high)
        quick_sort_random(arr, low, pi - 1)
        quick_sort_random(arr, pi + 1, high)


#── 3-way partition quick sort (duplicate element optimization) ───────────────────────────────────

def quick_sort_3way(arr: list[int], low: int, high: int) -> None:
    """3-way partition based on the Dutch National Flag.

    When there are many same values, O(n log n) → can become O(n).
    lt: end of the segment smaller than the pivot
    gt: start of the segment larger than the pivot"""
    if low >= high:
        return
    pivot = arr[low]
    lt = low        # arr[low..lt-1] < pivot
    gt = high       # arr[gt+1..high] > pivot
    i = low + 1     # arr[lt..i-1] == pivot

    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1

    quick_sort_3way(arr, low, lt - 1)
    quick_sort_3way(arr, gt + 1, high)


#── Worst case comparison ──────────────────────────────────────────────────────────────

def count_comparisons_basic(arr: list[int]) -> int:
    """Number of comparisons in basic quicksort (last element pivot) (simulation)."""

    count = [0]

    def _partition(a: list[int], lo: int, hi: int) -> int:
        pivot = a[hi]
        i = lo - 1
        for j in range(lo, hi):
            count[0] += 1
            if a[j] <= pivot:
                i += 1
                a[i], a[j] = a[j], a[i]
        a[i + 1], a[hi] = a[hi], a[i + 1]
        return i + 1

    def _qs(a: list[int], lo: int, hi: int) -> None:
        if lo < hi:
            pi = _partition(a, lo, hi)
            _qs(a, lo, pi - 1)
            _qs(a, pi + 1, hi)

    _qs(arr[:], 0, len(arr) - 1)
    return count[0]


#── Main ─────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    #Basic alignment test
    data = [3, 6, 8, 10, 1, 2, 1]
    arr1 = data[:]
    quick_sort_basic(arr1, 0, len(arr1) - 1)
    print(f"Basic quicksort: {data} → {arr1}")

    arr2 = data[:]
    quick_sort_random(arr2, 0, len(arr2) - 1)
    print(f"Random quick sort: {data} → {arr2}")

    arr3 = data[:]
    quick_sort_3way(arr3, 0, len(arr3) - 1)
    print(f"3-way quick sort: {data} → {arr3}")

    #Worst case comparison
    n = 100
    already_sorted = list(range(n))
    random_data = already_sorted[:]
    random.shuffle(random_data)

    cmp_sorted = count_comparisons_basic(already_sorted)
    cmp_random = count_comparisons_basic(random_data)
    print(f"\n=== Number of comparisons (n={n}) ===")
    print(f"Already sorted array (worst): {cmp_sorted:>6,} ≈ n²/2 = {n*n//2:,}")
    print(f"Random array (average): {cmp_random:>6,} ≈ n·log₂n ≈ {int(n*__import__('math').log2(n)):,}")

    #Arrangements with many duplicates — 3-way effect
    dup_data = [random.choice([1, 2, 3]) for _ in range(20)]
    arr4 = dup_data[:]
    quick_sort_3way(arr4, 0, len(arr4) - 1)
    print(f"\nDuplicate array 3-way: {dup_data}")
    print(f"             → {arr4}")

    #Accuracy Verification
    test = [random.randint(-50, 50) for _ in range(50)]
    a1 = test[:]
    quick_sort_random(a1, 0, len(a1) - 1)
    assert a1 == sorted(test), "Alignment error!"
    print("\nAccuracy Verification: PASS")

"""Topic  : Counting Sort & Radix Sort Concepts
Time   : Counting O(n+k), Radix O(nk)  (k = range of values or number of digits)
Space  : O(k)"""


#── Coefficient sorting ───────────────────────────────────────────────────────────────────

def counting_sort(arr: list[int]) -> list[int]:
    """Basic counting sort.

    Uses a count array with a range of k.
    However, all elements must be >= 0."""
    if not arr:
        return []
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for x in arr:
        count[x] += 1

    result: list[int] = []
    for val, cnt in enumerate(count):
        result.extend([val] * cnt)
    return result


def counting_sort_stable(arr: list[int], max_val: int) -> list[int]:
    """Stable coefficient sorting — preserves the order of elements.

    Using the prefix sum technique."""
    count = [0] * (max_val + 1)
    for x in arr:
        count[x] += 1

    #Cumulative sum
    for i in range(1, max_val + 1):
        count[i] += count[i - 1]

    output = [0] * len(arr)
    for x in reversed(arr):        #Reverse traversal → stable
        count[x] -= 1
        output[count[x]] = x

    return output


#── Cardinal sort (Decimal) ─────────────────────────────────────────────────────────

def radix_sort(arr: list[int]) -> list[int]:
    """LSD (Least Significant Digit) radix sort.

    Perform a stable counting sort for each digit.
    Time: O(d·(n+10))  d = number of digits, k=10 because it is decimal"""
    if not arr:
        return []
    a = arr[:]
    max_val = max(a)
    exp = 1          # 1, 10, 100, …
    while max_val // exp > 0:
        a = _counting_sort_by_digit(a, exp)
        exp *= 10
    return a


def _counting_sort_by_digit(arr: list[int], exp: int) -> list[int]:
    """Sort stability coefficients based on the exp-th digit."""
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for x in arr:
        digit = (x // exp) % 10
        count[digit] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    for x in reversed(arr):
        digit = (x // exp) % 10
        count[digit] -= 1
        output[count[digit]] = x

    return output


#── Visualization ─────────────────────────────────────────────────────────────────────

def visualize_counting(arr: list[int]) -> None:
    """Visualization of the counting sort process."""
    print(f"Input array: {arr}")
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for x in arr:
        count[x] += 1
    print(f"Count array: {count} (index = Value)")

    prefix = count[:]
    for i in range(1, max_val + 1):
        prefix[i] += prefix[i - 1]
    print(f"Cumulative sum array: {prefix}")

    result = counting_sort_stable(arr, max_val)
    print(f"Sort result: {result}")


def visualize_radix(arr: list[int]) -> None:
    """Radix sort digit-by-digit sorting process."""
    print(f"\nRadix sort input: {arr}")
    a = arr[:]
    max_val = max(a)
    exp = 1
    step = 1
    while max_val // exp > 0:
        a = _counting_sort_by_digit(a, exp)
        print(f"Digits 10^{step-1} (digits of {exp:>4}) After sorting: {a}")
        exp *= 10
        step += 1
    print(f"Final result: {a}")


#── Limitations and Applications ─────────────────────────────────────────────────────────────────

def when_to_use() -> None:
    """Guidance on suitable conditions for counting sort."""
    print("\n=== Coefficient sort usage conditions ===")
    examples = [
        ("Grade sorting (0~100)", 100, 10_000, "✅ k=100, n=10000 → O(n+k) = O(10100)"),
        ("Age sorting (1~120)", 120, 1_000_000, "✅ k=120, n=1M → Very efficient"),
        ("Social security number sorting (large range)", 999_999_999, 1_000, "❌ k≈1 billion → Memory exceeded"),
        ("Real value sorting", -1, 1000, "❌ Not available for real numbers"),
    ]
    for desc, k, n, verdict in examples:
        print(f"  {desc:30s}: {verdict}")


#── Main ────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    arr = [4, 2, 2, 8, 3, 3, 1, 7]

    print("=" * 50)
    print("Coefficient sorting visualization")
    print("=" * 50)
    visualize_counting(arr)

    sorted_basic = counting_sort(arr)
    print(f"\nBasic counting sorting result: {sorted_basic}")

    grades = [88, 74, 96, 88, 74, 100, 60]
    print(f"\nGrade coefficient sorting: {grades} → {counting_sort(grades)}")

    #Cardinal sort
    print("\n" + "=" * 50)
    print("Radix sorting visualization")
    print("=" * 50)
    big_nums = [170, 45, 75, 90, 802, 24, 2, 66]
    visualize_radix(big_nums)

    #Accuracy Verification
    import random
    test = [random.randint(0, 500) for _ in range(30)]
    assert counting_sort(test) == sorted(test), "Coefficient sorting error!"
    assert radix_sort(test) == sorted(test), "Radix sorting error!"
    print("\nAccuracy Verification: PASS")

    when_to_use()