Базовые сортировки

Зачем изучать простые сортировки?

Несмотря на то, что в реальном коде используются встроенные sort(), понимание базовых алгоритмов необходимо для: интервью, понимания более сложных алгоритмов, выбора алгоритма под конкретную задачу.

Пузырьковая сортировка (Bubble Sort)

Идея: сравниваем соседние элементы и меняем местами, если они в неправильном порядке. Большие элементы «всплывают» к концу.

<?php
declare(strict_types=1);

/** @param list<int> $arr */
function bubbleSort(array &$arr): void
{
    $n = count($arr);

    for ($i = 0; $i < $n; $i++) {
        $swapped = false;

        for ($j = 0; $j < $n - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                $swapped = true;
            }
        }

        if (!$swapped) {
            break; // Array is already sorted
        }
    }
}

func bubbleSort(arr []int) {
    n := len(arr)

    for i := 0; i < n; i++ {
        swapped := false

        for j := 0; j < n-1-i; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = true
            }
        }

        if !swapped {
            break // Array is already sorted
        }
    }
}

Проход 1: [5,3,8,1,2] -> [3,5,8,1,2] -> [3,5,8,1,2] -> [3,5,1,8,2] -> [3,5,1,2,8]
Проход 2: [3,5,1,2,8] -> [3,5,1,2,8] -> [3,1,5,2,8] -> [3,1,2,5,8]
Проход 3: [3,1,2,5,8] -> [1,3,2,5,8] -> [1,2,3,5,8]
Проход 4: [1,2,3,5,8] -> нет обменов -> СТОП

Сортировка выбором (Selection Sort)

Идея: на каждом шаге находим минимальный элемент и ставим на правильную позицию.

<?php
declare(strict_types=1);

/** @param list<int> $arr */
function selectionSort(array &$arr): void
{
    $n = count($arr);

    for ($i = 0; $i < $n; $i++) {
        $minIdx = $i;

        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$minIdx]) {
                $minIdx = $j;
            }
        }

        [$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]];
    }
}

func selectionSort(arr []int) {
    n := len(arr)

    for i := 0; i < n; i++ {
        minIdx := i

        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIdx] {
                minIdx = j
            }
        }

        arr[i], arr[minIdx] = arr[minIdx], arr[i]
    }
}

[5, 3, 8, 1, 2]
 i=0: min=1(idx=3), swap -> [1, 3, 8, 5, 2]
 i=1: min=2(idx=4), swap -> [1, 2, 8, 5, 3]
 i=2: min=3(idx=4), swap -> [1, 2, 3, 5, 8]
 i=3: min=5(idx=3), no swap -> [1, 2, 3, 5, 8]

Selection Sort делает минимальное количество обменов (n-1) — полезно, если swap дорогой.

Сортировка вставками (Insertion Sort)

Идея: берём элемент и вставляем его в правильное место среди уже отсортированной части. Как сортируешь карты в руке.

<?php
declare(strict_types=1);

/** @param list<int> $arr */
function insertionSort(array &$arr): void
{
    $n = count($arr);

    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;

        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }

        $arr[$j + 1] = $key;
    }
}

func insertionSort(arr []int) {
    n := len(arr)

    for i := 1; i < n; i++ {
        key := arr[i]
        j := i - 1

        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }

        arr[j+1] = key
    }
}

[5, 3, 8, 1, 2]
 |отсортировано|
 i=1: key=3, [5] > 3 -> сдвиг -> [3, 5, 8, 1, 2]
 i=2: key=8, 5 < 8 -> на месте -> [3, 5, 8, 1, 2]
 i=3: key=1, сдвиг 8,5,3 -> [1, 3, 5, 8, 2]
 i=4: key=2, сдвиг 8,5,3 -> [1, 2, 3, 5, 8]

Insertion Sort лучший из базовых: O(n) на почти отсортированных данных, стабильный, in-place, низкий overhead.

Сравнительная таблица

Adaptive — алгоритм быстрее на почти отсортированных данных.

Когда использовать базовые сортировки

• Insertion Sort: маленькие массивы (n < 50), почти отсортированные данные, online-сортировка (данные приходят потоком)
• Selection Sort: минимизация количества swap
• Bubble Sort: образовательные цели (на практике не используется)

Запомни: Insertion Sort — единственная из базовых, которую стоит использовать на практике. Встроенные sort() в Python (Timsort) и Go (pattern-defeating quicksort) используют Insertion Sort для маленьких подмассивов. Все базовые сортировки — in-place, O(1) памяти.

Итоги

1. Все базовые сортировки: O(n²) в среднем, O(1) памяти
2. Insertion Sort лучший из трёх: adaptive, stable, O(n) на почти отсортированных
3. Selection Sort: минимум swaps
4. Bubble Sort: только для обучения
5. На практике: sort() использует гибридные алгоритмы