Алгоритмы сортировки

def bubble_sort(a):
    a = a[:]
    for end in range(len(a) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if a[i] > a[i + 1]:                    # «всплываем» большой элемент вправо
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:                            # проход без обменов — уже отсортировано
            break
    return a

def insertion_sort(a):
    a = a[:]
    for i in range(1, len(a)):
        key, j = a[i], i - 1
        while j >= 0 and a[j] > key:               # сдвигаем большие вправо
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key                             # вставляем на место
    return a

def selection_sort(a):
    a = a[:]
    for i in range(len(a)):
        m = min(range(i, len(a)), key=a.__getitem__)    # ищем минимум в хвосте
        a[i], a[m] = a[m], a[i]
    return a

data = [5, 2, 9, 1, 5, 6]
print(bubble_sort(data), insertion_sort(data), selection_sort(data))

def merge(a, b):
    result, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:              # <= сохраняет устойчивость
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    return result + a[i:] + b[j:]

def merge_sort(a, depth=0):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid], depth + 1), merge_sort(a[mid:], depth + 1)
    merged = merge(left, right)
    print("  " * depth + f"слияние {left} + {right} → {merged}")
    return merged

merge_sort([38, 27, 43, 3, 9, 82, 10])

import random

def quick_sort_simple(a):
    if len(a) <= 1:
        return a
    pivot = random.choice(a)
    less = [x for x in a if x < pivot]
    equal = [x for x in a if x == pivot]
    greater = [x for x in a if x > pivot]
    return quick_sort_simple(less) + equal + quick_sort_simple(greater)

print(quick_sort_simple([3, 6, 8, 10, 1, 2, 1]))

def partition_lomuto(a, lo, hi):
    pivot = a[hi]
    i = lo                                 # граница «меньших»
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]              # опорный встаёт на своё итоговое место
    return i

arr = [7, 2, 1, 8, 6, 3, 5, 4]
p = partition_lomuto(arr, 0, len(arr) - 1)
print(arr, "опорный на позиции", p)

import random

def quickselect(a, k):
    """k-й наименьший (k от 0), в среднем O(n)."""
    a = a[:]
    lo, hi = 0, len(a) - 1
    while True:
        p = random.randint(lo, hi)
        a[p], a[hi] = a[hi], a[p]
        pivot, i = a[hi], lo
        for j in range(lo, hi):
            if a[j] < pivot:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[hi] = a[hi], a[i]
        if i == k:
            return a[i]
        if i < k:
            lo = i + 1
        else:
            hi = i - 1

data = [3, 2, 1, 5, 6, 4]
print(quickselect(data, len(data) - 2))     # второй по величине

def counting_sort(a, max_value):
    counts = [0] * (max_value + 1)
    for x in a:
        counts[x] += 1
    result = []
    for value, c in enumerate(counts):
        result.extend([value] * c)
    return result

ages = [25, 31, 18, 25, 40, 18, 22]
print(counting_sort(ages, 120))              # O(n + k), k — диапазон значений

def radix_sort(a):
    """Поразрядная сортировка неотрицательных чисел: устойчиво по каждой цифре."""
    exp = 1
    while max(a, default=0) // exp > 0:
        buckets = [[] for _ in range(10)]
        for x in a:
            buckets[(x // exp) % 10].append(x)
        a = [x for b in buckets for x in b]
        exp *= 10
    return a

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

people = [("Анна", "HR", 150), ("Боря", "IT", 250), ("Вера", "IT", 200), ("Глеб", "HR", 150)]

print(sorted(people, key=lambda p: p[2], reverse=True))
print(sorted(people, key=lambda p: (p[1], -p[2])))        # отдел ↑, зарплата ↓

by_name = sorted(people, key=lambda p: p[0], reverse=True)   # устойчивость: сортируем по
by_dept = sorted(by_name, key=lambda p: p[1])                 # второстепенному, потом по главному
print(by_dept)

words = ["banana", "apple", "Cherry", "date"]
print(sorted(words), sorted(words, key=str.lower), sorted(words, key=len))