Сортировка была готовым инструментом — теперь разберём её работу

В блоке про интервалы мы пользовались Array.Sort как знакомой операцией: упорядочивали бронирования по началу или заявки по окончанию и дальше работали с уже упорядоченным массивом. Тогда это было удобно и уместно: нас интересовала логика объединения или отбора, а не механика упорядочивания. Но теперь настало время открыть коробку и посмотреть, что внутри. Как именно массив становится упорядоченным? Какие приёмы для этого используют и чем они отличаются друг от друга? Начнём с одного из самых простых, но от этого не менее поучительного способа.

Возьмём массив цен: [5, 3, 4, 5, 2]. Нужно расположить их по неубыванию: меньшие вперёд, большие назад. Заметьте важную деталь: мы сохраняем все значения и их кратности. Если в исходном массиве было две пятёрки, в результате их тоже должно быть две. Сортировка не удаляет и не изменяет элементы — она только переставляет их местами. Об этом полезно помнить, потому что иногда встречается соблазн «упростить» данные, выбросив лишнее, и это уже не сортировка, а что-то другое.

С чего начать? С простой идеи: на первое место в результате должен встать самый маленький элемент. Давайте его найдём и поставим в начало. Потом на второе место — следующий по величине. И так далее, пока не расставим все. Это и есть сортировка выбором: на каждом шаге выбираем минимум из ещё не отсортированной части и ставим его в начало этой части.

Разберём шаг подробнее. Пусть мы уже поставили на свои места первые i элементов. Оставшаяся часть массива — это позиции с i по n − 1. Среди них нужно найти минимум. Проходим по ним и запоминаем индекс наименьшего элемента. Обратите внимание: мы ищем именно индекс, а не значение. Значение мы и так знаем, как только нашли индекс; но именно индекс нам понадобится для обмена.

Когда проход закончен, у нас есть minIndex — индекс минимального элемента в хвосте. Теперь нужно поставить его на позицию i. Меняем местами a[i] и a[minIndex]. На этом шаг завершён. Первые i + 1 позиций теперь содержат i + 1 наименьших элементов в правильном порядке.

Здесь есть тонкость, на которой легко споткнуться. Иногда в процессе поиска минимума мы встречаем всё более и более маленькие элементы — и рука тянется обменять прямо сейчас, не дожидаясь конца прохода. Делать так не стоит. Обмен на каждом уменьшении создаёт лишнюю работу: элементов может быть много, а обмен — дорогое действие. Мы должны дождаться окончания прохода и сделать ровно один обмен — только тогда, когда точно знаем, какой элемент является минимумом. Если minIndex совпал с i, обмен вообще не нужен: элемент уже на своём месте. Проверка на разные индексы не даёт лишней работы и не портит ничего.

Сформулируем, на чём держится корректность. После завершения шага с номером i первые i + 1 позиций массива содержат i + 1 наименьших элементов исходного массива, расположенных в неубывающем порядке. А все остальные элементы — от позиции i + 1 и дальше — не меньше последнего элемента отсортированного префикса. Это инвариант, и он сохраняется на каждом шаге.

Почему? На шаге i мы искали минимум среди a[i..n). Все элементы, которые уже стоят в префиксе, меньше или равны любому из оставшихся: они были выбраны на предыдущих шагах как минимумы своих хвостов. Значит, найденный минимум — это следующий по величине элемент всего массива. Ставим его на позицию i, и инвариант продолжает выполняться. Когда i доходит до n − 1, весь массив отсортирован.

Прогоним на нашем массиве [5, 3, 4, 5, 2]. Шаг i = 0: ищем минимум в [5, 3, 4, 5, 2]. Начинаем с предположения, что минимум — это a[0] = 5. Сравниваем с a[1] = 3: 3 меньше, minIndex = 1. С a[2] = 4: не меньше. С a[3] = 5: не меньше. С a[4] = 2: 2 меньше, minIndex = 4. Проход закончен. Меняем a[0] и a[4]: получаем [2, 3, 4, 5, 5].

Шаг i = 1: ищем минимум в [3, 4, 5, 5] (позиции 1..4). Начинаем с a[1] = 3. Сравниваем с a[2] = 4: не меньше. С a[3] = 5: не меньше. С a[4] = 5: не меньше. minIndex = 1, совпадает с i. Обмена не делаем — элемент уже на месте.

Шаг i = 2: ищем минимум в [4, 5, 5]. a[2] = 4 — минимум, обмена нет.

Шаг i = 3: ищем минимум в [5, 5]. minIndex = 3, обмена нет.

Массив отсортирован: [2, 3, 4, 5, 5]. Важно понять, что отсутствие обменов на шагах 1–3 не означает, что алгоритм завершился раньше. Он честно прошёл все проходы до конца. Просто в этих проходах минимум уже стоял на своём месте. Алгоритм не «догадывается», что массив отсортирован, — он всегда выполняет все n − 1 шагов.

Программа SelectionSort

Соберём это в код. Функция принимает массив и сортирует его на месте, ничего не возвращая: результат виден в самом массиве. Случай null отсекаем отдельно.

using System;

int[] prices = { 5, 3, 4, 5, 2 };
SelectionSort(prices);
Print(prices);

int[] empty = Array.Empty<int>();
SelectionSort(empty);
Print(empty);

int[] one = { 7 };
SelectionSort(one);
Print(one);

int[] negative = { -3, 5, -1, 0, -3 };
SelectionSort(negative);
Print(negative);

int[] duplicates = { 4, 4, 4 };
SelectionSort(duplicates);
Print(duplicates);

void SelectionSort(int[] a)
{
    if (a == null) throw new ArgumentNullException(nameof(a));
    int n = a.Length;
    for (int i = 0; i < n - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < a[minIndex]) minIndex = j;
        }
        if (minIndex != i)
        {
            int tmp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = tmp;
        }
    }
}

void Print(int[] a)
{
    if (a.Length == 0)
    {
        Console.WriteLine("(пусто)");
        return;
    }
    Console.WriteLine(string.Join(" ", a));
}

Вывод:

2 3 4 5 5
(пусто)
7
-3 -3 -1 0 5
4 4 4

Разберём случаи. Основной массив [5, 3, 4, 5, 2] отсортирован в [2, 3, 4, 5, 5], как мы и проследили. Пустой массив: цикл не выполняется, на экране «(пусто)». Один элемент: сортировать нечего, остаётся 7. Отрицательные числа сортируются так же, как положительные: сравнение работает с любыми int. Массив [−3, 5, −1, 0, −3] превращается в [−3, −3, −1, 0, 5]. Все три четвёрки остаются на месте: они уже упорядочены, и обменов не происходит.

Посчитаем сравнения. На шаге i мы проходим по хвосту a[i+1..n), то есть делаем n − i − 1 сравнений. Просуммируем по всем i от 0 до n − 2: получаем (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. Это ровно столько, сколько даёт наш код, и столько же — в любом порядке входных данных. Сортировка выбором не ускоряется на почти отсортированных массивах: она всегда делает одинаковое число сравнений. Лучший случай совпадает с худшим — O(n²).

Обменов — не больше n − 1: по одному на каждый шаг внешнего цикла, и то не всегда. Вспомогательная память — O(1): только индексы и временная переменная для обмена. Массив сортируется на месте.

О стабильности

Теперь о свойстве, которое не бросается в глаза, но важно в некоторых задачах. Представьте, что элементы массива — это не просто числа, а объекты с ключом сортировки и дополнительными данными. У двух элементов может быть один и тот же ключ, но разное содержимое. Скажем, [2A, 2B, 1C]: здесь 2A и 2B — два разных объекта с ключом 2, а 1C — объект с ключом 1.

Что произойдёт при сортировке выбором? Сначала на позицию 0 встанет 1C — это минимум. Обмен: a[0] = 2A меняется местами с a[2] = 1C. Получаем [1C, 2B, 2A]. Замечаете? Относительный порядок 2A и 2B изменился: раньше 2A шёл первым, теперь первым идёт 2B. Сортировка выбором не сохраняет взаимный порядок равных элементов.

Такое свойство называется стабильностью. Сортировка стабильна, если элементы с одинаковыми ключами сохраняют свой относительный порядок из исходного массива. Выбором — не стабильна: обмен через дальнюю позицию может переставить равные элементы. В некоторых задачах это неважно — когда важен только ключ. В других — критично: например, если сначала отсортировали по одному признаку, а потом по другому и хотим, чтобы первый признак сохранился как вторичный. Мы будем учитывать это в дальнейшем.

Ещё одна мысль, которая пригодится и дальше. Если мы хотим убедиться, что сортировка работает правильно, недостаточно проверить, что результат упорядочен. Можно «отсортировать» массив, потеряв элементы или заменив их другими, и результат всё равно окажется неубывающим. Например, заменить [5, 3, 4, 5, 2] на [2, 3, 4, 5, 6] — упорядоченность есть, а исходных данных больше нет.

Настоящая проверка состоит из двух частей. Во-первых, результат должен быть упорядочен по неубыванию: a[i] ≤ a[i+1] для всех i. Во-вторых, результат должен быть перестановкой исходного массива: те же элементы с теми же кратностями, ни одного потерянного и ни одного лишнего. Проверить это можно, например, отсортировав копию исходного массива другой сортировкой и сравнив поэлементно — но это уже отдельная техника, и она понадобится нам, когда будем тестировать свои реализации. Сейчас достаточно держать в голове саму идею: сортировка обязана сохранить данные.

Мы разобрали один способ сортировки — простой и наглядный. Он делает ровно n(n − 1)/2 сравнений и n − 1 обменов в худшем случае, и этого достаточно, чтобы увидеть его квадратичную природу. Существуют другие сортировки, в том числе такие, которые работают быстрее и умеют сохранять стабильность. Но сравнивать с ними сейчас преждевременно: мы ещё не разобрали их устройство. Стоит также оговориться, что не всякая квадратичная сортировка делает именно n(n − 1)/2 сравнений — у разных квадратичных алгоритмов свои точные счётчики, и обобщать наш результат на всех не стоит. В следующих уроках мы разберём другие подходы, и тогда можно будет сравнивать осмысленно.