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

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

Несмотря на то, что в реальном коде используются встроенные 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
        }
    }
}

// In production code you would call Array.Sort(arr) (introsort).
// This implementation is for learning the algorithm itself.
static void BubbleSort(int[] arr)
{
    int n = arr.Length;

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

        for (int 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
        }
    }
}

# In production code you would call arr.sort() / sorted(arr) (Timsort).
# This implementation is for learning the algorithm itself.
def bubble_sort(arr: list[int]) -> None:
    n = len(arr)

    for i in range(n):
        swapped = False

        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        if not swapped:
            break  # Array is already sorted

Визуализация (сортировка [5, 3, 8, 1, 2]):

Проход 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] -> нет обменов -> СТОП

Сложность	Лучший	Средний	Худший
Время	O(n)	O(n²)	O(n²)
Память	O(1)	O(1)	O(1)
Стабильная	Да

Сортировка выбором (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]
    }
}

static void SelectionSort(int[] arr)
{
    int n = arr.Length;

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

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

        (arr[i], arr[minIdx]) = (arr[minIdx], arr[i]);
    }
}

def selection_sort(arr: list[int]) -> None:
    n = len(arr)

    for i in range(n):
        min_idx = i

        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j

        arr[i], arr[min_idx] = arr[min_idx], 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]

Сложность	Лучший	Средний	Худший
Время	O(n²)	O(n²)	O(n²)
Память	O(1)	O(1)	O(1)
Стабильная	Нет

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
    }
}

static void InsertionSort(int[] arr)
{
    int n = arr.Length;

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

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

        arr[j + 1] = key;
    }
}

def insertion_sort(arr: list[int]) -> None:
    n = len(arr)

    for i in range(1, n):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        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]

Сложность	Лучший	Средний	Худший
Время	O(n)	O(n²)	O(n²)
Память	O(1)	O(1)	O(1)
Стабильная	Да

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

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

Алгоритм	Лучший	Средний	Худший	Память	Стабильный	Adaptive
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Да	Да
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	Нет	Нет
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Да	Да

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) памяти.

Итоги

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