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

Сортировка — это процесс упорядочивания элементов по определённому правилу: по возрастанию, по убыванию, по алфавиту, по дате и так далее. Без сортировки не обходится ни одна программа:

• Магазин: товары отсортированы по цене или рейтингу
• Соцсеть: посты отсортированы по дате публикации
• Поисковик: результаты отсортированы по релевантности
• Банк: транзакции отсортированы по дате и сумме
• Игры: таблица лидеров отсортирована по очкам

Алгоритм сортировки — это пошаговая инструкция, которая гарантированно упорядочивает массив. Алгоритмов десятки, и каждый имеет свои сильные и слабые стороны.

Основные критерии, по которым сравнивают алгоритмы:

1. Скорость работы — сколько операций нужно выполнить
2. Потребление памяти — нужна ли дополнительная память
3. Стабильность — сохраняется ли порядок равных элементов
4. In-place vs not-in-place — сортируется ли массив на месте

Чтобы оценивать скорость алгоритмов, компьютерные учёные придумали Big O нотацию. Давай разберёмся, как она работает.

Big O (О-большое) — это математическая нотация, которая описывает, как растёт время выполнения алгоритма при увеличении количества входных данных. Она показывает асимптотическую сложность — то есть поведение на больших объёмах данных.

Представь, что n — это количество элементов. Big O отвечает на вопрос: «Если я увеличу n в 10 раз, во сколько раз медленнее станет алгоритм?»

Основные классы сложности (от лучшего к худшему):

Визуализация роста сложности (n = 1 000 000):

Сложность   n = 10     n = 100    n = 1000    n = 1 000 000
─────────────────────────────────────────────────────────────────
O(1)         1 оп      1 оп       1 оп        1 оп
O(log n)     4 оп      7 оп       10 оп       20 оп
O(n)         10 оп     100 оп     1000 оп     1 000 000 оп
O(n log n)   33 оп     664 оп     9966 оп     19 931 569 оп
O(n²)        100 оп    10 000 оп  1 000 000 оп ≈ 1 000 000 000 000 оп

Big O нотация отбрасывает константы и младшие слагаемые. Например, 5n² + 3n + 10 — это всё равно O(n²). Нас интересует только самый быстрорастущий член.

У каждого алгоритма сортировки есть две важные характеристики: временная сложность (сколько операций) и пространственная сложность (сколько дополнительной памяти).

Алгоритмы можно разделить на три категории:

• Квадратичные O(n²) — простые, но медленные: пузырёк, вставка, выбор
• Линейно-логарифмические O(n log n) — быстрые: быстрая сортировка, слияние, пирамидальная
• Линейные O(n) — особые случаи: сортировка подсчётом (для чисел с ограниченным диапазоном)

Сводная таблица популярных алгоритмов:

Стабильная сортировка сохраняет относительный порядок элементов с одинаковыми ключами. Звучит сложно, но на примере всё просто.

Представь, что у нас есть список студентов, отсортированный по имени, и мы хотим отсортировать его по возрасту:

Исходный список (отсортирован по имени):
Анна, 25
Борис, 22
Вика, 25
Глеб, 22

После стабильной сортировки по возрасту:
Борис, 22    // первым из 22-летних
Глеб, 22     // вторым из 22-летних (сохранился порядок из исходного)
Анна, 25     // первой из 25-летних
Вика, 25     // второй из 25-летних (сохранился порядок)

После нестабильной сортировки по возрасту:
Глеб, 22     // или Борис — порядок не гарантирован
Борис, 22
Вика, 25     // или Анна — порядок не гарантирован
Анна, 25

Когда важна стабильность? Когда ты сортируешь данные по нескольким полям последовательно. Например, сначала по дате, потом по статусу. Со стабильной сортировкой вторая сортировка не «сломает» порядок первой.

Важно: встроенная сортировка C# (Introsort) нестабильна. Если нужна стабильная сортировка — используй LINQ OrderBy() (она стабильна) или Merge Sort.

In-place (сортировка на месте) — алгоритм использует только O(1) или O(log n) дополнительной памяти. Массив сортируется прямо в той же области памяти.

Not-in-place (с внешней памятью) — алгоритм создаёт новые массивы для промежуточных результатов. Требует O(n) дополнительной памяти.

Для большинства практических задач C# использует Introsort — гибридный алгоритм, который работает in-place. Но если тебе нужно сохранить исходный порядок, используй OrderBy(), который создаёт копию.

В C# для сортировки не нужно писать свой алгоритм (если, конечно, это не учебная задача). В стандартной библиотеке есть две основные точки входа:

int[] arr = { 5, 2, 8, 1, 9 };

// Array.Sort() — in-place сортировка массива (Introsort)
Array.Sort(arr);
Console.WriteLine(string.Join(", ", arr));  // 1, 2, 5, 8, 9

// List.Sort() — in-place сортировка списка (Introsort)
var list = new List<int> { 5, 2, 8, 1, 9 };
list.Sort();
Console.WriteLine(string.Join(", ", list)); // 1, 2, 5, 8, 9

// LINQ OrderBy() — not-in-place, возвращает новую коллекцию
var sorted = arr.OrderBy(x => x).ToArray();
Console.WriteLine(string.Join(", ", sorted)); // 1, 2, 5, 8, 9
// Исходный arr при этом не меняется!

Introsort (Introspective Sort) — это гибридный алгоритм, который используется в Array.Sort() и List.Sort(). Он был разработан Дэвидом Массером в 1997 году и объединяет три алгоритма:

1. Quick Sort — основной алгоритм. Работает в среднем за O(n log n).
2. Heap Sort — подключается, если Quick Sort начинает деградировать (глубина рекурсии слишком большая). Гарантирует O(n log n) в худшем случае.
3. Insertion Sort — для маленьких подмассивов (< 16 элементов). Быстрее всех на малых данных.

Благодаря этой комбинации Introsort гарантирует O(n log n) в худшем случае, но при этом быстр в среднем — как Quick Sort.

В 99% случаев тебе не нужно писать свою сортировку. Встроенный Introsort (через Array.Sort() или List.Sort()) справляется отлично. Вот когда его достаточно:

1. Обычные данные — числа, строки, даты, простые объекты
2. Любой размер — от 10 до 10 000 000 элементов (Introsort оптимизирован для всех размеров)
3. Не нужна стабильность — если порядок равных элементов не важен
4. Сортировка по нескольким полям — используй LINQ OrderBy().ThenBy()
5. Стандартные типы — int, double, string, DateTime уже умеют сравниваться

Когда нужно писать свою сортировку:

• Учебные задачи — чтобы понять, как работают алгоритмы
• Особые структуры данных — например, частично отсортированные массивы
• Ограничения по памяти — если доступно меньше O(log n) дополнительной памяти
• Специфические требования — сортировка на GPU, внешняя сортировка для файлов

Часто нужно сортировать не числа, а объекты. Например, список пользователей по возрасту или товаров по цене. Для этого используется либо LINQ, либо интерфейс IComparable<T>:

class Product
{
    public string Name { get; set; }
    public double Price { get; set; }
    public int Rating { get; set; }
}

var products = new List<Product>
{
    new Product { Name = "Ноутбук",  Price = 120000, Rating = 5 },
    new Product { Name = "Мышь",     Price = 2500,   Rating = 4 },
    new Product { Name = "Клавиатура", Price = 5000, Rating = 5 },
};

// Сортировка по цене (LINQ OrderBy)
var byPrice = products.OrderBy(p => p.Price);
foreach (var p in byPrice)
    Console.WriteLine($"{p.Price} — {p.Name}");
// 2500 — Мышь
// 5000 — Клавиатура
// 120000 — Ноутбук

// Сортировка по рейтингу, а потом по цене (ThenBy)
var byRatingThenPrice = products
    .OrderByDescending(p => p.Rating)
    .ThenBy(p => p.Name);
foreach (var p in byRatingThenPrice)
    Console.WriteLine($"{p.Name}: рейтинг {p.Rating}, цена {p.Price}");

// In-place сортировка с компаратором (лямбда)
products.Sort((a, b) => a.Price.CompareTo(b.Price));
// Теперь products отсортирован по цене

Разберём, как работает компаратор: Sort((a, b) => a.Price.CompareTo(b.Price)).

• Если a.Price меньше b.Price → CompareTo вернёт < 0 → a будет раньше b
• Если равны → вернёт 0 → порядок не меняется
• Если больше → вернёт > 0 → a будет позже b
• Для сортировки по убыванию: products.Sort((a, b) => b.Price.CompareTo(a.Price))

Иногда нужно отсортировать данные в обратном порядке (по убыванию). Вот как это сделать:

int[] arr = { 5, 2, 8, 1, 9 };

// Способ 1: отсортировать по возрастанию, затем развернуть
Array.Sort(arr);
Array.Reverse(arr);
Console.WriteLine(string.Join(", ", arr));  // 9, 8, 5, 2, 1

// Способ 2: через LINQ OrderByDescending
var desc = arr.OrderByDescending(x => x).ToArray();
// arr не изменился, desc = { 9, 8, 5, 2, 1 }

// Способ 3: обратный компаратор
Array.Sort(arr, (a, b) => b.CompareTo(a));
// arr отсортирован по убыванию

Проверь, как ты усвоил основы алгоритмов сортировки.