Сортировка и бинарный поиск

Сортировка и бинарный поиск

В Go не нужно писать сортировку с нуля. Но нужно понимать, когда какой подход работает, чем Slice отличается от SliceStable, и почему один и тот же массив сортируется за разное время на разных версиях Go.

sort.Slice - быстрая сортировка

nums := []int{5, 3, 1, 4, 2}
sort.Slice(nums, func(i, j int) bool {
    return nums[i] < nums[j]
})
// [1, 2, 3, 4, 5]

// Сортировка структур
type User struct {
    Name string
    Age  int
}

users := []User{
    {"Bob", 30}, {"Alice", 25}, {"Carol", 35},
}

sort.Slice(users, func(i, j int) bool {
    return users[i].Age < users[j].Age
})

sort.Slice использует reflection один раз для получения swap-функции, поэтому немного медленнее sort.Sort с sort.Interface. На горячем пути это может быть заметно.

<?php
declare(strict_types=1);

$nums = [5, 3, 1, 4, 2];
sort($nums); // [1, 2, 3, 4, 5] - in-place, переиндексирует

// Сортировка структур через usort + spaceship operator <=>
final readonly class User
{
    public function __construct(public string $name, public int $age) {}
}

$users = [
    new User('Bob', 30),
    new User('Alice', 25),
    new User('Carol', 35),
];

usort($users, static fn (User $a, User $b): int => $a->age <=> $b->age);
// [Alice 25, Bob 30, Carol 35]

В PHP - sort() (числа/строки in-place), usort() (с компаратором), asort() (сохраняя ключи), ksort() (по ключам).

from dataclasses import dataclass

nums = [5, 3, 1, 4, 2]
nums.sort()  # in-place; sorted(nums) вернёт новый список
# [1, 2, 3, 4, 5]


# Сортировка структур - через key-функцию, а не компаратор
@dataclass(slots=True)
class User:
    name: str
    age: int


users = [
    User("Bob", 30), User("Alice", 25), User("Carol", 35),
]

users.sort(key=lambda u: u.age)
# [Alice 25, Bob 30, Carol 35]

list.sort() и sorted() принимают key, а не компаратор: key вычисляется один раз на элемент (n вызовов), компаратор - на каждое сравнение (n log n). Компаратор в стиле usort подключается через functools.cmp_to_key, но нужен редко.

Оператор <=> (spaceship) возвращает -1/0/1 - именно то, что ждёт usort. Это аналог cmp.Compare из Go 1.21.

sort.Interface - для повторного использования

type ByName []User

func (a ByName) Len() int           { return len(a) }
func (a ByName) Less(i, j int) bool { return a[i].Name < a[j].Name }
func (a ByName) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

sort.Sort(ByName(users))

Когда один и тот же тип сортируется в разных местах - выноси sort.Interface в reusable тип.

<?php
declare(strict_types=1);

final class UserComparator
{
    public static function byName(User $a, User $b): int
    {
        return $a->name <=> $b->name;
    }

    public static function byAge(User $a, User $b): int
    {
        return $a->age <=> $b->age;
    }

    /** Multi-key: сначала по возрасту, потом по имени */
    public static function byAgeThenName(User $a, User $b): int
    {
        return $a->age <=> $b->age
            ?: $a->name <=> $b->name;
    }
}

usort($users, UserComparator::byName(...)); // PHP 8.1+ first-class callable syntax

В PHP компараторы вытаскивают в final class со статическими методами или в invokable-объекты - удобно тестировать.

from operator import attrgetter

# Переиспользуемые key-функции вместо sort.Interface:
# attrgetter быстрее lambda и читается как декларация
by_name = attrgetter("name")
by_age = attrgetter("age")
# Multi-key: сначала по возрасту, потом по имени
by_age_then_name = attrgetter("age", "name")

users.sort(key=by_name)

Когда один и тот же тип сортируется в разных местах - выноси key-функции в константы модуля рядом с классом. Тестировать их проще, чем компараторы: одна функция - одно значение.

UserComparator::byName(...) - PHP 8.1+ синтаксис «first-class callable». До этого писали [UserComparator::class, 'byName'] или замыкание.

Бинарный поиск

// Через sort.Search (возвращает индекс первого элемента, где f(i) == true)
nums := []int{1, 3, 5, 7, 9, 11}
target := 7

idx := sort.Search(len(nums), func(i int) bool {
    return nums[i] >= target
})

if idx < len(nums) && nums[idx] == target {
    fmt.Printf("Найден на позиции %d\n", idx)
}

// С Go 1.21: slices.BinarySearch
import "slices"

idx, found := slices.BinarySearch(nums, target)

slices.BinarySearch короче и не требует замыкания. Работает только с упорядоченными типами (cmp.Ordered).

<?php
declare(strict_types=1);

/**
 * Бинарный поиск на отсортированном массиве.
 * @return int Индекс или -1, если не найдено.
 */
function binarySearch(array $nums, int $target): int
{
    $lo = 0;
    $hi = count($nums) - 1;

    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($nums[$mid] === $target) {
            return $mid;
        }
        if ($nums[$mid] < $target) {
            $lo = $mid + 1;
        } else {
            $hi = $mid - 1;
        }
    }

    return -1;
}

$nums = [1, 3, 5, 7, 9, 11];
$idx = binarySearch($nums, 7); // 3

В PHP native бинарного поиска нет - array_search() это O(n) линейный обход. Если данные отсортированы и поиск горячий - реализуй вручную.

from bisect import bisect_left

# Через bisect_left (возвращает индекс первого элемента >= target) -
# прямой аналог sort.Search
nums = [1, 3, 5, 7, 9, 11]
target = 7

idx = bisect_left(nums, target)

if idx < len(nums) and nums[idx] == target:
    print(f"Найден на позиции {idx}")


# Аналога slices.BinarySearch с флагом found в stdlib нет - обёртка в три строки
def binary_search(nums: list[int], target: int) -> tuple[int, bool]:
    idx = bisect_left(nums, target)
    return idx, idx < len(nums) and nums[idx] == target


idx, found = binary_search(nums, target)

Модуль bisect - это только поиск позиции; bisect_left и bisect_right отличаются тем, куда встанет дубликат. bisect.insort вставляет с сохранением порядка, но сама вставка в список O(n).

array_search($needle, $arr) всегда O(n), не используй его как замену бинарного поиска. Для частых поисков на отсортированном наборе - либо ручная реализация, либо переход на hash-структуру (isset($index[$key]), O(1)).

Как устроены сортировки из таблицы

Сначала коротко - что делают алгоритмы, которые встретятся в таблице ниже.

  • Bubble sort (пузырёк) и insertion sort (вставками) - простые O(n²): пузырёк много раз проходит массив и меняет местами соседей, стоящих не по порядку; вставками берёт элементы по одному и вдвигает каждый на своё место в уже отсортированное начало.
  • Quicksort выбирает опорный элемент (pivot), раскладывает массив на «меньше опорного» и «больше опорного» (partition) и рекурсивно сортирует обе части. На удачных опорных части примерно равны, и выходит O(n log n); если опорный раз за разом оказывается минимумом или максимумом, части вырождаются в «ничего» и «всё остальное» - это худший случай O(n²).

Quicksort пошагово: pivot, partition, рекурсия по половинам

Merge sort и откуда берётся n log n

Merge sort (сортировка слиянием) делает наоборот: сначала делит, потом наводит порядок.

  1. Делим массив пополам, каждую половину сортируем тем же способом (рекурсивно), пока не останутся куски из одного элемента - они уже отсортированы.
  2. Сливаем две отсортированные половины в одну. Слияние идёт двумя указателями: по одному на начало каждой половины. Сравниваем два элемента под указателями, меньший кладём в результат и двигаем его указатель. Когда одна половина кончилась, хвост другой дописываем целиком. Каждый элемент перекладывается один раз, поэтому слияние кусков общей длиной n стоит O(n).
слить [1 4 7] и [2 3 9]:
 1<2 → 1     4>2 → 2     4>3 → 3     4<9 → 4     7<9 → 7     хвост → 9
итог: [1 2 3 4 7 9]

Откуда n log n: деление пополам даёт log₂ n уровней, а на каждом уровне все слияния вместе перекладывают ровно n элементов. Итого n на каждом из log₂ n уровней - O(n log n), причём в любом случае, не только в среднем. Цена - буфер под результат слияния, O(n) дополнительной памяти. При равных элементах слияние берёт элемент из левой половины первым, поэтому merge sort стабилен (что это значит - в разделе о стабильной сортировке).

Сравнение алгоритмов

АлгоритмСреднееХудшееПамятьСтабильный
Bubble SortO(n²)O(n²)O(1)Да
Insertion SortO(n²)O(n²)O(1)Да
Merge SortO(n log n)O(n log n)O(n)Да
Quick SortO(n log n)O(n²)O(log n)Нет
sort.Slice (Go)O(n log n)O(n log n)O(log n)Нет

С Go 1.19 sort.Slice использует pdqsort (pattern-defeating quicksort) - гибрид рекурсивных quicksort и heapsort:

  • быстрый quicksort на типичных данных;
  • переключается в heapsort при подозрении на adversarial input → гарантирует O(n log n) в худшем случае;
  • использует insertion sort на маленьких подмассивах (до 12 элементов), где он быстрее из-за cache locality;
  • детектирует уже отсортированные/обратно отсортированные участки и обрабатывает их за O(n).

На реальных данных это даёт 2-3× ускорение против старого sort.Sort (introsort).

С PHP 8.0 sort/usort стабильны: внутренний гибрид quicksort и insertion sort (zend_sort) остался прежним, но при равенстве элементов теперь учитывается их исходный порядок. Отдельного стабильного варианта больше не нужно. Особого ускорения на уже отсортированных данных, как у Timsort в Python, нет: сложность остаётся O(n log n).

Грубые ориентиры по скорости

На современном x86 ядре slices.Sort для []int:

РазмерВремя
1 000~30 мкс
100 000~5 мс
1 000 000~60 мс

Цифры зависят от распределения данных, типа элементов и компаратора. Всегда замеряй через go test -bench на своём профиле - не доверяй ориентирам.

Стабильная сортировка

Стабильная сортировка сохраняет относительный порядок равных элементов. Важно при multi-key sort: сначала сортируешь по фамилии, потом по департаменту - фамилии внутри департамента остаются упорядоченными только при стабильной сортировке.

// sort.Slice - НЕ стабильная (равные элементы могут поменять порядок)
// sort.SliceStable - стабильная, но заметно медленнее: in-place слияние
// без буфера, O(n log² n) перестановок, на больших слайсах в разы
sort.SliceStable(users, func(i, j int) bool {
    return users[i].Age < users[j].Age
})

Не платишь за стабильность, когда она не нужна - Slice быстрее.

В PHP 8.0+ usort стабилен по умолчанию (тот же zend_sort, но с учётом исходного порядка при равенстве) - отдельного «stable»-варианта не нужно. На PHP 7.x для стабильной сортировки добавляли индекс в компаратор как tiebreaker. Если код должен работать на legacy-версиях - см. ниже.

<?php
declare(strict_types=1);

// PHP 8.0+ - просто usort, оно уже stable
usort($users, static fn (User $a, User $b): int => $a->age <=> $b->age);

// Legacy-trick для PHP < 8.0: добавить индекс как tiebreaker
$indexed = array_map(
    static fn (int $i, User $u): array => ['idx' => $i, 'user' => $u],
    array_keys($users),
    $users,
);
usort($indexed, static fn (array $a, array $b): int =>
    $a['user']->age <=> $b['user']->age
        ?: $a['idx'] <=> $b['idx']
);
$users = array_column($indexed, 'user');
# list.sort и sorted - ВСЕГДА стабильные (Timsort), отдельного варианта нет
users.sort(key=lambda u: u.age)

# Поэтому multi-key sort делают двумя проходами: сначала вторичный ключ,
# потом первичный - стабильность сохранит порядок внутри групп
users.sort(key=lambda u: u.name)
users.sort(key=lambda u: u.age)

Нет и «нестабильного, но быстрого» режима - Timsort и так работает за O(n) на уже упорядоченных участках, так что платить за стабильность не приходится.

Counting / Radix sort: когда обходят O(n log n)

Граница O(n log n) фундаментальна только для сортировок сравнением. Если знаешь диапазон значений - есть линейные алгоритмы.

Counting sort

Для целых в небольшом диапазоне (например, возраст 0-150):

func countingSort(nums []int, maxVal int) []int {
    count := make([]int, maxVal+1)
    for _, v := range nums {
        count[v]++
    }
    out := make([]int, 0, len(nums))
    for v, c := range count {
        for ; c > 0; c-- {
            out = append(out, v)
        }
    }
    return out
}
<?php
declare(strict_types=1);

/**
 * @param array<int> $nums
 * @return array<int>
 */
function countingSort(array $nums, int $maxVal): array
{
    $count = array_fill(0, $maxVal + 1, 0);
    foreach ($nums as $v) {
        $count[$v]++;
    }

    $out = [];
    foreach ($count as $value => $cnt) {
        for ($i = 0; $i < $cnt; $i++) {
            $out[] = $value;
        }
    }
    return $out;
}
def counting_sort(nums: list[int], max_val: int) -> list[int]:
    count = [0] * (max_val + 1)
    for v in nums:
        count[v] += 1
    out: list[int] = []
    for v, c in enumerate(count):
        out.extend([v] * c)  # c копий значения v одним вызовом
    return out

Время - O(n + k), где k - диапазон значений. На сортировке миллиона возрастов работает в разы быстрее quicksort.

Radix sort

Разбивает ключ на разряды и применяет counting sort по каждому. Используется в специализированных библиотеках (например, golang.org/x/exp/slices экспериментирует с radix). В стандартной библиотеке нет - слишком ситуативно.

Пакет slices (Go 1.21+)

import "slices"

nums := []int{3, 1, 4, 1, 5}
slices.Sort(nums)                  // сортировка
slices.SortStableFunc(nums, cmp.Compare) // стабильная с компаратором
slices.SortFunc(nums, cmp.Compare) // нестабильная с компаратором
slices.Contains(nums, 4)           // O(n) поиск
slices.Index(nums, 4)              // индекс или -1
slices.Min(nums)                   // минимум
slices.Max(nums)                   // максимум
slices.BinarySearch(nums, 4)       // O(log n) на отсортированном

Новый API быстрее старого sort за счёт generics - нет reflection. Используй slices в новом коде, sort - только для совместимости с sort.Interface библиотек.

В PHP набор аналогичных функций давно встроен в ядро:

<?php
declare(strict_types=1);

$nums = [3, 1, 4, 1, 5];

sort($nums);                                  // [1, 1, 3, 4, 5] - in-place
$copy = $nums; sort($copy);                   // сортировка копии

usort($nums, fn($a, $b) => $a <=> $b);        // с компаратором (stable с PHP 8.0)

in_array(4, $nums, strict: true);             // O(n) поиск
$idx = array_search(4, $nums, strict: true);  // O(n), индекс или false
min($nums);                                    // минимум
max($nums);                                    // максимум

// asort/ksort/uasort/uksort - вариации с сохранением ключей
asort($users);   // сортирует значения, сохраняет ключи
ksort($users);   // сортирует по ключам

Аналоги разбросаны по встроенным функциям и модулю bisect:

from bisect import bisect_left

nums = [3, 1, 4, 1, 5]
nums.sort()                        # сортировка in-place
sorted(nums, key=lambda v: v)      # копия, стабильная, с key-функцией
# нестабильного варианта нет: Timsort всегда стабилен
4 in nums                          # O(n) поиск
nums.index(4)                      # индекс или ValueError (не -1)
min(nums)                          # минимум
max(nums)                          # максимум
bisect_left(nums, 4)               # O(log n) на отсортированном

В PHP массивы имеют семантику значения (копия при присваивании, реализованная через copy-on-write), а сортировка написана на C и reflection не использует. На крупных датасетах разница с Go измеримая, но для типичных HTTP-запросов это не bottleneck.

Когда какой выбор

СценарийAPI
[]int, []string в новом кодеslices.Sort
Структура, простой компараторslices.SortFunc
Нужна стабильностьslices.SortStableFunc
Один и тот же тип в 5+ местахsort.Sort с sort.Interface
Числа в малом диапазоне, миллион элементовcounting sort вручную
Найти k-й элемент без полной сортировкиcontainer/heap или quickselect
Поиск в отсортированномslices.BinarySearch

Типичные ошибки

1. Неправильное направление Less

// БАГ: возвращает по убыванию, хотя задумано по возрастанию
sort.Slice(nums, func(i, j int) bool {
    return nums[i] > nums[j] // > вместо <
})
<?php
declare(strict_types=1);

// PHP-аналог: путаница в знаке spaceship-оператора
// БАГ: $b - $a сортирует по убыванию вместо возрастания
usort($nums, static fn (int $a, int $b): int => $b <=> $a); // DESC, не ASC

// Правильно - $a <=> $b для возрастания:
usort($nums, static fn (int $a, int $b): int => $a <=> $b);
from functools import cmp_to_key

# БАГ: перепутаны a и b в компараторе - сортирует по убыванию
nums.sort(key=cmp_to_key(lambda a, b: b - a))  # DESC, не ASC

# Или забытый reverse=True, оставшийся от соседнего отчёта
nums.sort(reverse=True)

# Правильно - просто nums.sort(): с key-функцией знак перепутать негде
nums.sort()

Less должен вернуть true, когда элемент i должен идти раньше j.

2. Сортировка float с NaN

nums := []float64{1.0, math.NaN(), 2.0}
sort.Float64s(nums) // NaN портит порядок
<?php
declare(strict_types=1);

// PHP - то же поведение: NAN не сравнивается ни с чем.
$nums = [1.0, NAN, 2.0];
sort($nums); // порядок NAN не определён, нарушает сортировку

// Фильтрация NAN до сортировки:
$nums = array_values(array_filter($nums, static fn (float $v): bool => !is_nan($v)));
sort($nums);

// Или кастомный компаратор - NAN в конец:
usort($nums, static function (float $a, float $b): int {
    if (is_nan($a)) return 1;
    if (is_nan($b)) return -1;
    return $a <=> $b;
});
import math

# То же поведение: nan не сравнивается ни с чем, sort молча портит порядок
nums = [1.0, math.nan, 2.0]
nums.sort()  # NaN портит порядок

# Фильтрация NaN до сортировки:
nums = [v for v in nums if not math.isnan(v)]
nums.sort()

# Или key-функция - NaN в конец: кортежи сравниваются поэлементно,
# False < True, поэтому все nan уходят в хвост
nums.sort(key=lambda v: (math.isnan(v), v))

NaN не сравнивается ни с чем (NaN < x всегда false). Фильтруй NaN до сортировки или используй кастомный компаратор с math.IsNaN.

3. Бинарный поиск в неотсортированном слайсе

idx, found := slices.BinarySearch([]int{3, 1, 4, 1, 5}, 1)
// found == false, хотя 1 есть в слайсе дважды
<?php
declare(strict_types=1);

// PHP-эквивалент: ручной binarySearch без проверки сортировки в рантайме
$nums = [3, 1, 4, 1, 5]; // НЕ отсортирован
$idx = binarySearch($nums, 1); // -1, хотя 1 есть в массиве дважды

// Защитный паттерн: проверка в dev-окружении
// (assert отключается в production через zend.assertions=-1)
$sorted = $nums;
sort($sorted);
assert($nums === $sorted, 'binarySearch requires sorted input');

// Или forsorted-обёртка, гарантирующая контракт:
final class SortedIntArray
{
    public function __construct(private readonly array $items)
    {
        $copy = $items;
        sort($copy);
        if ($items !== $copy) {
            throw new InvalidArgumentException('Input must be sorted');
        }
    }
}
from bisect import bisect_left

nums = [3, 1, 4, 1, 5]  # НЕ отсортирован
idx = bisect_left(nums, 1)
found = idx < len(nums) and nums[idx] == 1
# found == False, хотя единица есть в списке дважды


# Защитный паттерн - обёртка, проверяющая контракт при создании:
class SortedInts:
    def __init__(self, items: list[int]) -> None:
        if items != sorted(items):
            raise ValueError("input must be sorted")
        self._items = items

    def search(self, target: int) -> tuple[int, bool]:
        idx = bisect_left(self._items, target)
        return idx, idx < len(self._items) and self._items[idx] == target

BinarySearch ожидает отсортированный вход - это контракт API, не проверяется в рантайме.

Зарегистрируйтесь бесплатно, чтобы пройти квиз, решить задание с автопроверкой, вести прогресс.