Сортировка 1: пузырьком, выбором и вставками

Сортировка выбором делает ровно 45 сравнений на любом списке из 10 значений, перемешан ли он вначале или уже упорядочен.

Расставляем по порядку

Сортировать значит переставлять значения списка так, чтобы они шли от меньшего к большему (или по имени, дате, цене, в любом порядке, который можно сравнивать). Это одна из самых частых работ компьютера: контакты в телефоне, результаты поиска по релевантности, столбец таблицы по дате. Сортировка облегчает и другие задачи. Как показал прошлый урок, в отсортированном списке можно искать двоичным поиском, а повторы в отсортированном списке стоят рядом.

В этом уроке три простых способа. Все три сравнивают по два значения за раз и переставляют значения внутри того же списка. Их коротко писать и легко понять, и все три резко замедляются на длинных списках. Если понять, почему они замедляются, легче разобраться в быстрых способах из следующего урока. Всё время мы считаем две вещи: сравнения (вопрос «это значение больше того?») и обмены (два значения меняются местами).

Сортировка пузырьком: меняем местами соседей не по порядку

Сортировка пузырьком идёт вдоль списка и сравнивает каждую пару соседей. Если левый больше, она меняет их местами. После одного полного прохода наибольшее значение шаг за шагом доезжает до правого края, как всплывающий пузырёк, и больше ему двигаться не нужно. Следующий проход может остановиться на одно место раньше. Частое улучшение: следить за проходом без единого обмена. Это значит, что всё уже по порядку, и сортировку можно закончить раньше.

Проследим на списке [5, 1, 4, 2, 8]. Первый проход сравнивает 5 и 1 (обмен), 5 и 4 (обмен), 5 и 2 (обмен), 5 и 8 (оставляем): список стал [1, 4, 2, 5, 8], и 8 на месте. Второй проход сравнивает 1 и 4, 4 и 2 (обмен), 4 и 5, получается [1, 2, 4, 5, 8]. Третий проход сравнивает 1 и 2, затем 2 и 4, обменов нет, и сортировка останавливается. Итого: 4 + 3 + 2 = 9 сравнений и 4 обмена.

function bubbleSort(a) {
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let j = 0; j < a.length - 1 - pass; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];  // обмен
        swapped = true;
      }
    }
    if (!swapped) break;  // уже отсортирован
  }
  return a;
}

Сортировка выбором: найди наименьшее и поставь следующим

Сортировка выбором работает так, как многие люди раскладывают карты в руке. Просмотри весь список, найди наименьшее значение и обменяй его на первую позицию. Затем просмотри остаток, найди наименьшее из оставшихся и обменяй его на вторую позицию, и так далее. На [5, 1, 4, 2, 8] первый просмотр находит 1 и меняет его с 5; второй находит 2 и меняет его с 5; последние два просмотра находят 4 и 5 уже на месте. Это всего 2 обмена, но просмотры всё равно делают 4 + 3 + 2 + 1 = 10 сравнений.

Сортировка выбором никогда не останавливается раньше. Даже на уже отсортированном списке ей всё равно нужно проверить каждое оставшееся значение, чтобы убедиться, что найдено наименьшее. Для n значений сравнения всегда в сумме дают (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. Для 10 значений это 45; для 100 значений 4950; для 1000 значений 499 500. Её сильная сторона в малом числе обменов: не больше n − 1, и это важно, когда перемещать значение дорого.

Сортировка вставками: вставь каждое новое значение на место

Сортировка вставками держит левую часть списка отсортированной и наращивает её по одному значению. Она берёт следующее значение и двигает его влево, меняя с соседом, пока сосед не окажется не больше. Тогда значение стоит на своём месте среди отсортированных. На почти упорядоченном списке каждое новое значение сдвигается лишь на шаг-два, поэтому там сортировка вставками очень быстрая. На [5, 1, 4, 2, 8] она делает 7 сравнений и 4 обмена.

Считаем обмены: инверсии

Есть изящный способ предсказать, сколько обменов нужно сортировке пузырьком и вставками. Посчитай инверсии: пары значений, которые стоят в неправильном порядке относительно друг друга. В [5, 1, 4, 2, 8] инверсии (5, 1), (5, 4), (5, 2) и (4, 2), всего четыре. Каждый обмен двух соседей, стоящих не по порядку, исправляет ровно одну инверсию и не создаёт новых, поэтому оба способа делают ровно 4 обмена. В обратном списке из n значений инвертирована каждая пара, n(n − 1)/2 инверсий, и это худший случай.

В каждой ячейке: сравнения / обмены. Пример списка: [5, 1, 4, 2, 8]. Сортировка пузырьком здесь в варианте, который останавливается после прохода без обмена.

У всех трёх способов одна и та же слабость. В худшем случае каждый сравнивает примерно каждую пару значений, около n²/2 сравнений. Удвой список, и работа вырастет в четыре раза. Список в десять раз длиннее означает в сто раз больше работы. Для нескольких десятков значений это почти не важно; для миллиона это безнадёжно, и следующий урок показывает, как сделать гораздо лучше.