🔴 Сложный ⏱️ 50 минут

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

📋 Содержание урока

Алгоритмы сортировки 🔃

В предыдущих уроках ты разбирал алгоритмы Дейкстры, Крускала и Прима — и в каждом из них незаметно пряталась одна и та же операция. Алгоритм Дейкстры на каждом шаге выбирает вершину с минимальным расстоянием. Крускал сначала сортирует все рёбра графа по весу и только потом жадно их перебирает. Даже поиск минимального остовного дерева на практике почти всегда начинается со слов «отсортируем рёбра». Сортировка — это не экзотическая надстройка над алгоритмами, а один из самых фундаментальных строительных блоков информатики, на который явно или неявно опирается огромная доля всего остального.

Специалисту по данным сортировка встречается гораздо чаще, чем может показаться на первый взгляд. Когда дерево решений ищет лучший порог разбиения по числовому признаку — например, «разделить клиентов по возрасту так, чтобы группы были максимально однородны по целевой переменной» — алгоритм на практике сортирует значения признака по возрастанию и затем проходит по этому отсортированному списку, проверяя пороги между соседними значениями. Без сортировки перебор всех возможных порогов был бы намного дороже. Когда метод k ближайших соседей ищет $k$ самых близких точек к запросу, самый прямолинейный способ — вычислить расстояния до всех точек обучающей выборки и отсортировать их по возрастанию, а затем взять первые $k$. Ты вызываешь sklearn.tree.DecisionTreeClassifier или sklearn.neighbors.KNeighborsClassifier, не думая о сортировке ни секунды, но под капотом она там есть — и от того, насколько быстро она работает, зависит, обучится твоя модель за секунду или за час.

В этом уроке ты разберёшь три самых простых, самых старых и самых наглядных алгоритма сортировки: сортировку выбором, сортировку пузырьком и сортировку вставками. Все три работают за $O(n^2)$ в худшем случае, и именно поэтому в промышленном коде для больших массивов их почти никогда не используют напрямую — быстрая сортировка и сортировка слиянием, которым посвящены следующие два урока, справляются асимптотически лучше. Но было бы ошибкой считать эти три алгоритма просто «устаревшими» или «учебными». У них есть две характеристики, которые часто решают исход дела на практике куда сильнее, чем голая асимптотика: устойчивость сортировки (сохраняет ли она относительный порядок элементов с равными ключами — свойство, на котором держится многоуровневая сортировка DataFrame.sort_values(by=[...]) в pandas) и то, работает ли алгоритм на месте (не требуя дополнительной памяти, пропорциональной размеру входных данных, или требуя).

К концу урока ты будешь понимать не только «как работает» каждый из трёх алгоритмов, но и почему один из них никогда не используется в реальном коде, а другой — наоборот, спрятан внутри почти каждой современной библиотечной реализации сортировки, включая ту, что стоит за sorted() в Python и Array.prototype.sort в JavaScript. Ты также увидишь, что «квадратичный» не значит «плохой везде и всегда» — для маленьких массивов и почти отсортированных данных простые алгоритмы иногда побеждают более сложные асимптотически быстрые подходы.

История: от перфокарт до Timsort

Задача сортировки — одна из самых древних в информатике, и она старше самих компьютеров в современном понимании. Ещё в конце XIX века Герман Холлерит построил табуляционные машины для обработки данных переписи населения США 1890 года, и среди их операций была механическая сортировка перфокарт по отверстиям — задача, знакомая нам сегодня как сортировка записей по ключу, решалась буквально физическими механизмами задолго до появления электронных вычислителей. Сортировка карточных каталогов, документов, платёжных ведомостей — задача упорядочивания данных существовала в делопроизводстве веками, компьютеры лишь автоматизировали то, что клерки и библиотекари делали вручную.

Сами алгоритмы, которые разбираются в этом уроке, настолько интуитивны, что люди используют их варианты неосознанно. Сортировка вставками — это буквально то, как большинство людей раскладывают карты в руке при игре: берут следующую карту и вставляют её в уже упорядоченную часть руки на нужное место. Именно поэтому первые формальные описания подобных алгоритмов в ранней литературе по программированию 1950-х годов звучали скорее как формализация уже известной житейской процедуры, а не как изобретение чего-то принципиально нового. Название «сортировка пузырьком» появилось позже — один из первых документированных терминов для этого метода («сортировка обменом», sorting by exchange) встречается в статье 1956 года, а закрепившееся сегодня название отражает то, как крупные элементы будто «всплывают» к своему месту за несколько проходов, словно пузырьки воздуха в жидкости.

Систематизировал и каталогизировал десятки вариаций алгоритмов сортировки Дональд Кнут в третьем томе своей монументальной серии «Искусство программирования» (1973), целиком посвящённом сортировке и поиску. Именно оттуда происходит теперь широко цитируемая ирония в адрес сортировки пузырьком: Кнут отмечал, что у неё нет практически никаких преимуществ, кроме запоминающегося названия, — и с точки зрения производительности это почти буквально так, дальше в уроке ты увидишь почему на конкретных числах. При этом сортировка вставками избежала подобной судьбы «алгоритма только для учебников»: её адаптивность к почти упорядоченным данным оказалась настолько ценной, что в 2002 году Тим Питерс, разрабатывая для Python алгоритм Timsort (сегодня используемый и в Python, и в Java для сортировки объектов, и в Android), встроил вставочную сортировку как «базовый случай» — часть, отвечающую за сортировку маленьких кусков массива внутри намного более сложной гибридной схемы. Об этом стоит помнить весь урок: то, что алгоритм «плохой» асимптотически, не значит, что он бесполезен — иногда он просто работает не на переднем плане, а спрятан внутри чего-то более быстрого.

Сортировка выбором: находим минимум и ставим его на место

Интуиция

Представь, что тебе нужно расставить книги на полке по возрастанию номера страниц, а книги свалены в стопку рядом. Самый прямолинейный подход: просмотреть всю стопку, найти самую «тонкую» книгу, положить её на полку первой; затем просмотреть оставшуюся часть стопки, найти следующую самую тонкую, положить её второй — и так далее, пока стопка не закончится. На каждом шаге ты выбираешь минимальный элемент из ещё не отсортированной части и ставишь его сразу на финальное место. Отсюда и название — сортировка выбором (selection sort): на каждой итерации ты явно выбираешь минимум среди оставшихся элементов.

Ключевая особенность этого подхода в том, что как только элемент поставлен на своё место, он там и остаётся — алгоритм никогда больше к нему не возвращается. Массив мысленно делится на две части: слева — уже отсортированный и зафиксированный «хвост из отсортированных значений», справа — ещё не тронутая часть, из которой продолжается поиск минимума.

Алгоритм

Алгоритм сортировки выбором.

Для каждой позиции $i$ от $0$ до $n-2$:

Найти индекс минимального элемента среди $A[i \ldots n-1]$

Поменять местами $A[i]$ и найденный минимальный элемент

Перейти к следующей позиции $i+1$

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Примеры с разбором

Пример 1. Полная трассировка. Массив: $[64, 25, 12, 22, 11]$.

i=0: минимум среди [64,25,12,22,11] — это 11 (индекс 4). Меняем A[0] и A[4]:
     [11, 25, 12, 22, 64]
i=1: минимум среди [25,12,22,64] — это 12 (индекс 2). Меняем A[1] и A[2]:
     [11, 12, 25, 22, 64]
i=2: минимум среди [25,22,64] — это 22 (индекс 3). Меняем A[2] и A[3]:
     [11, 12, 22, 25, 64]
i=3: минимум среди [25,64] — это 25 (индекс 3, уже на месте). Обмена нет:
     [11, 12, 22, 25, 64]

Итог: $[11, 12, 22, 25, 64]$, выполнено ровно $3$ реальных обмена (на четвёртом шаге минимум уже стоял на своём месте).

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

i=0: сравниваем A[0] с A[1],A[2],A[3],A[4] — 4 сравнения, минимум найден на месте
i=1: сравниваем A[1] с A[2],A[3],A[4] — 3 сравнения
i=2: сравниваем A[2] с A[3],A[4] — 2 сравнения
i=3: сравниваем A[3] с A[4] — 1 сравнение
Итого: 4+3+2+1 = 10 сравнений = n(n-1)/2 при n=5

Число сравнений получилось ровно таким же, как было бы для полностью перемешанного массива того же размера — сортировка выбором всегда просматривает всю оставшуюся часть на каждом шаге, независимо от того, упорядочены данные или нет. Это значит, что лучший, средний и худший случаи у неё совпадают: все три — $\Theta(n^2)$ по числу сравнений. Такой алгоритм называют неадаптивным: он не умеет использовать «удачливость» входных данных.

Пример 3. Сортировка выбором ломает относительный порядок равных элементов. Возьмём массив пар (значение, метка), где метка нужна только для того, чтобы отследить, что происходит с одинаковыми значениями: $[(2, \text{'x'}), (2, \text{'y'}), (1, \text{'z'})]$.

i=0: минимум по значению среди всех трёх пар — (1,'z') на индексе 2.
     Меняем местами A[0] и A[2]:
     [(1,'z'), (2,'y'), (2,'x')]
i=1: минимум среди A[1],A[2] — оба значения равны 2, min_idx остаётся 1
     (так как строгое "<" не срабатывает при равенстве). Обмена нет:
     [(1,'z'), (2,'y'), (2,'x')]

До сортировки пара со значением $2$ и меткой 'x' шла раньше пары со значением $2$ и меткой 'y'. После сортировки порядок стал обратным: 'y' оказалась перед 'x'. Это произошло из-за самого обмена на первом шаге — он «перепрыгнул» через 'y' и поменял местами элементы, не стоящие рядом. Значит, сортировка выбором в своём обычном виде неустойчива — этот факт станет важен в разделе про устойчивость сортировки.

Почему это важно

Главное практическое достоинство сортировки выбором — не скорость (она такая же квадратичная, как у соседей по уроку), а минимальное число операций записи: массив из $n$ элементов сортируется не более чем за $n-1$ обменов, независимо от того, насколько он был перемешан изначально. Это резко отличает её от сортировки пузырьком, которая может выполнить $O(n^2)$ обменов. Когда операция записи значительно дороже операции сравнения — например, при перестановке крупных записей во внешней памяти или при сортировке данных на носителях с ограниченным числом циклов перезаписи — минимизация количества обменов может перевешивать более высокую асимптотику по сравнениям.

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

Интуиция

Сортировка пузырьком — самый прямолинейный из трёх алгоритмов: сравнивай каждую пару соседних элементов и меняй их местами, если они стоят не по порядку. За один полный проход по массиву самый большой ещё не зафиксированный элемент гарантированно «всплывёт» до своей финальной позиции в конце — точно так же, как пузырёк воздуха поднимается к поверхности жидкости. После первого прохода на своём месте гарантированно стоит как минимум один элемент (самый большой), после второго — как минимум два, и так далее, пока весь массив не будет упорядочен.

Алгоритм

Алгоритм сортировки пузырьком (с ранним выходом).

Для каждого прохода $i$ от $0$ до $n-2$:

Установить флаг swapped = False

Для каждого $j$ от $0$ до $n-i-2$: если $A[j] > A[j+1]$, поменять их местами и установить swapped = True

Если за весь проход не было ни одного обмена — массив уже отсортирован, завершить работу досрочно

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

Примеры с разбором

Пример 1. Полная трассировка. Массив: $[5, 1, 4, 2, 8]$.

Проход 1 (i=0, сравниваем пары j=0..3):
  (5,1) -> 5>1, меняем:  [1, 5, 4, 2, 8]
  (5,4) -> 5>4, меняем:  [1, 4, 5, 2, 8]
  (5,2) -> 5>2, меняем:  [1, 4, 2, 5, 8]
  (5,8) -> 5<8, без изменений: [1, 4, 2, 5, 8]

Проход 2 (i=1, сравниваем пары j=0..2):
  (1,4) -> без изменений
  (4,2) -> 4>2, меняем:  [1, 2, 4, 5, 8]
  (4,5) -> без изменений

Проход 3 (i=2, сравниваем пары j=0..1):
  (1,2) -> без изменений
  (2,4) -> без изменений
  обменов не было -> ранний выход

Итог: $[1, 2, 4, 5, 8]$, получен за $3$ прохода вместо возможных $4$ благодаря флагу раннего выхода.

Пример 2. Ранний выход на почти отсортированных данных. Массив: $[1, 2, 3, 5, 4]$ — единственная «неправильная» пара в конце.

Проход 1 (i=0, j=0..3), 4 сравнения:
  (1,2) нет, (2,3) нет, (3,5) нет, (5,4) -> меняем: [1, 2, 3, 4, 5]
  swapped=True, продолжаем

Проход 2 (i=1, j=0..2), 3 сравнения:
  (1,2) нет, (2,3) нет, (3,4) нет
  swapped=False -> ранний выход!

Всего выполнено $4 + 3 = 7$ сравнений вместо $4+3+2+1=10$, которые потребовались бы без флага раннего выхода. На уже отсортированном массиве оптимизированная сортировка пузырьком выполнит всего один проход и $n-1$ сравнений — это и есть лучший случай $O(n)$, который принципиально отличает её от неадаптивной сортировки выбором из предыдущего раздела.

Пример 3. Устойчивость сортировки пузырьком. Массив пар: $[(2, \text{'x'}), (2, \text{'y'}), (1, \text{'z'})]$.

Проход 1 (i=0, j=0..1):
  ((2,'x'),(2,'y')): 2>2 — ложно (строгое сравнение), обмена нет
  ((2,'y'),(1,'z')): 2>1 — меняем: [(2,'x'), (1,'z'), (2,'y')]

Проход 2 (i=1, j=0..0):
  ((2,'x'),(1,'z')): 2>1 — меняем: [(1,'z'), (2,'x'), (2,'y')]

Итог: $[(1,\text{'z'}), (2,\text{'x'}), (2,\text{'y'})]$. Обрати внимание: пара с меткой 'x' по-прежнему стоит перед парой с меткой 'y' — точно так же, как и в исходном массиве. Это не случайность: сортировка пузырьком меняет местами только соседние элементы и только при строгом неравенстве, поэтому два равных значения никогда не поменяются местами друг с другом. Значит, сортировка пузырьком устойчива — в отличие от сортировки выбором из предыдущего раздела.

Почему это важно

Практическая ценность сортировки пузырьком сегодня почти целиком образовательная: она нагляднее всего демонстрирует саму идею компаратора и обмена, на ней удобнее всего впервые вводить понятие инварианта цикла («после $i$-го прохода последние $i$ элементов уже на своих местах») и доказательство корректности через этот инвариант. В промышленном коде её не используют почти никогда — при том же классе сложности $O(n^2)$ она обычно проигрывает сортировке вставками по количеству реальных операций и почти всегда проигрывает по устойчивому кэш-поведению. Но как учебная модель для понимания того, что вообще значит «алгоритм сортировки» и «инвариант», она остаётся незаменимой.

Сортировка вставками: строим отсортированную часть постепенно

Интуиция

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

Алгоритм

Алгоритм сортировки вставками.

Для каждой позиции $i$ от $1$ до $n-1$:

Сохранить $key = A[i]$

Сдвигать вправо все элементы $A[j]$ при $j < i$, пока $A[j] > key$

Вставить $key$ на освободившееся место

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Примеры с разбором

Пример 1. Полная трассировка. Массив: $[12, 11, 13, 5, 6]$.

i=1, key=11: A[0]=12>11 -> сдвигаем 12 вправо, вставляем 11 на позицию 0
             [11, 12, 13, 5, 6]
i=2, key=13: A[1]=12<13 -> сдвигов нет, 13 остаётся на месте
             [11, 12, 13, 5, 6]
i=3, key=5:  A[2]=13>5, A[1]=12>5, A[0]=11>5 -> сдвигаем все три,
             вставляем 5 на позицию 0
             [5, 11, 12, 13, 6]
i=4, key=6:  A[3]=13>6, A[2]=12>6, A[1]=11>6, A[0]=5<6 -> сдвигаем три,
             вставляем 6 на позицию 1
             [5, 6, 11, 12, 13]

Итог: $[5, 6, 11, 12, 13]$.

Пример 2. Адаптивность на почти отсортированных данных. Массив: $[1, 2, 4, 3, 5]$ — единственная соседняя пара стоит неправильно.

i=1, key=2: A[0]=1<2 -> сравнений: 1, сдвигов нет
i=2, key=4: A[1]=2<4 -> сравнений: 1, сдвигов нет
i=3, key=3: A[2]=4>3 -> сдвигаем 4; A[1]=2<3 -> стоп.
            сравнений: 2, сдвигов: 1
            [1, 2, 3, 4, 5]
i=4, key=5: A[3]=4<5 -> сравнений: 1, сдвигов нет

Всего $1+1+2+1 = 5$ сравнений для массива из $5$ элементов — против $10$ сравнений в худшем случае ($n(n-1)/2$). Это и есть адаптивность: чем ближе массив к уже отсортированному состоянию, тем быстрее сортировка вставками с ним справляется, вплоть до $O(n)$ на полностью отсортированном входе. Ни сортировка выбором, ни сортировка пузырьком без флага раннего выхода такого свойства не имеют.

Пример 3. Устойчивость сортировки вставками. Массив пар: $[(3, \text{'a'}), (1, \text{'b'}), (3, \text{'c'})]$.

i=1, key=(1,'b'): A[0]=(3,'a'), 3>1 -> сдвигаем; j=-1, стоп.
                  вставляем (1,'b') на позицию 0:
                  [(1,'b'), (3,'a'), (3,'c')]
i=2, key=(3,'c'): A[1]=(3,'a'), сравнение по значению: 3>3 — ложно
                  (строгое неравенство), сдвига нет, (3,'c') остаётся
                  на позиции 2:
                  [(1,'b'), (3,'a'), (3,'c')]

Итог: $[(1,\text{'b'}), (3,\text{'a'}), (3,\text{'c'})]$. Относительный порядок пары со значением $3$ — 'a' по-прежнему перед 'c', как и в исходном массиве. Условие сдвига использует строгое «$>$», поэтому элемент никогда не сдвигается мимо равного себе — сортировка вставками устойчива, как и сортировка пузырьком, но в отличие от сортировки выбором.

Почему это важно

Сортировка вставками — единственный из трёх квадратичных алгоритмов, который реально живёт внутри современных промышленных библиотек, а не только в учебниках. Её адаптивность (быстро на почти упорядоченных данных) и низкие константные издержки на маленьких массивах делают её идеальным «базовым случаем» внутри гибридных алгоритмов: Timsort использует вставочную сортировку для упорядочивания коротких «прогонов» (runs) длиной около $32$–$64$ элементов перед их слиянием, а типичные реализации быстрой сортировки (включая std::sort в C++) переключаются на вставочную сортировку, когда рекурсивный подмассив становится совсем маленьким. Здесь же — практический сценарий «онлайн-сортировки»: если данные поступают по одному элементу за раз (например, обновляемый рейтинг лидеров), вставочную сортировку удобно применять инкрементально, вставляя каждый новый элемент сразу на нужное место, не пересортировывая всё с нуля.

Устойчивость сортировки: почему порядок равных элементов важен

Интуиция

Представь таблицу сотрудников с колонками «отдел» и «зарплата», и тебе нужно отсортировать её сначала по отделу, а внутри каждого отдела — по зарплате по возрастанию. Формально задача решается элегантным трюком: сначала выполни устойчивую сортировку по второстепенному ключу (зарплате), а затем — устойчивую сортировку по главному ключу (отделу). Устойчивость второй сортировки гарантирует, что внутри каждой группы одинаковых отделов порядок, установленный первой сортировкой по зарплате, не будет разрушен. Это не абстрактная теория — именно так внутри работает DataFrame.sort_values(by=['department', 'salary']) в pandas при сортировке по нескольким столбцам: результат корректен именно потому, что базовая процедура сортировки, применяемая к ключам, устойчива.

Определение. Сортировка называется устойчивой (stable), если для любых двух элементов с равными ключами их относительный порядок в отсортированном массиве совпадает с их относительным порядком во входном массиве.

Из трёх алгоритмов этого урока сортировка пузырьком и сортировка вставками устойчивы в своей стандартной реализации (это ты уже видел на трассировках выше), а сортировка выбором — нет.

Примеры с разбором

Пример 1. Устойчивая сортировка сохраняет вторичный порядок при равных ключах. Записи об экзамене (балл, имя): $[(85, \text{'Иван'}), (90, \text{'Ольга'}), (85, \text{'Борис'})]$. Применим сортировку вставками по баллу.

i=1, key=(90,'Ольга'): A[0]=(85,'Иван'), 85>90 — ложно, сдвига нет
i=2, key=(85,'Борис'): A[1]=(90,'Ольга'), 90>85 — сдвигаем;
                       A[0]=(85,'Иван'), 85>85 — ложно, стоп.
                       вставляем на позицию 1:
                       [(85,'Иван'), (85,'Борис'), (90,'Ольга')]

Оба человека с баллом $85$ — Иван и Борис — стояли в этом порядке до сортировки, и в этом же порядке они стоят после. Устойчивая сортировка не выбирает произвольно, кого поставить первым при равенстве: она честно сохраняет исходный порядок.

Пример 2. Многоуровневая сортировка через два последовательных устойчивых прохода. Записи (предмет, балл): [('Мат',70), ('Физ',85), ('Мат',90), ('Физ',70)]. Нужно сгруппировать по предмету, а внутри предмета отсортировать баллы по возрастанию.

Шаг 1. Устойчиво сортируем по баллу (второстепенный ключ):
  ключи баллов: 70, 85, 90, 70
  результат: [('Мат',70), ('Физ',70), ('Физ',85), ('Мат',90)]
  (у двух записей с баллом 70 порядок 'Мат' перед 'Физ' сохранён —
   таким он был в исходном массиве)

Шаг 2. Устойчиво сортируем результат шага 1 по предмету (главный ключ,
  алфавитный порядок кириллицы: 'Мат' раньше 'Физ'):
  элементы 'Мат' в том порядке, как они шли после шага 1: (Мат,70),(Мат,90)
  элементы 'Физ' в том порядке, как они шли после шага 1: (Физ,70),(Физ,85)
  итог: [('Мат',70), ('Мат',90), ('Физ',70), ('Физ',85)]

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

Пример 3. То же самое кодом, с прямым выходом на pandas.

students = [('Мат', 70), ('Физ', 85), ('Мат', 90), ('Физ', 70)]

# способ 1: два последовательных устойчивых прохода
step1 = sorted(students, key=lambda s: s[1])   # сначала по баллу
result = sorted(step1, key=lambda s: s[0])     # затем по предмету

# способ 2: один проход с составным ключом-кортежем — даёт тот же результат,
# потому что сравнение кортежей в Python лексикографическое
result_v2 = sorted(students, key=lambda s: (s[0], s[1]))

print(result)     # [('Мат', 70), ('Мат', 90), ('Физ', 70), ('Физ', 85)]
print(result_v2)  # тот же самый список

Встроенная в Python функция sorted() реализована на основе Timsort и гарантированно устойчива — это официально задокументированное свойство языка, а не случайность реализации. Ровно на этой же гарантии строится df.sort_values(by=['department', 'salary']) в pandas: передавая список столбцов, ты фактически просишь библиотеку применить ту же логику «сначала по младшим ключам, затем по старшим» — и получаешь корректный результат именно потому, что базовая сортировка устойчива.

Почему это важно

Устойчивость — это ровно то свойство, без которого многоуровневая сортировка данных (сортировка таблицы сразу по нескольким столбцам, что в data science — обыденная операция) была бы либо невозможна без явного составного ключа, либо давала бы недетерминированный, непредсказуемый результат при равных значениях. Кроме pandas это касается SQL (ORDER BY по нескольким колонкам), сортировки логов с одинаковыми временными метками (нужно сохранить порядок поступления), ранжирования результатов поиска при равном скоринге и вообще любой ситуации, где «одинаковые по одному критерию» объекты всё равно должны идти в предсказуемом порядке.

Сортировка на месте против дополнительной памяти

Интуиция

Представь, что нужно расставить книги на одной и той же полке по алфавиту, не имея второй полки для черновика — только сама полка и, может быть, одна свободная рука, чтобы временно подержать одну книгу во время перестановки. Это и есть сортировка на месте (in-place): алгоритму требуется лишь $O(1)$ дополнительной памяти сверх самого входного массива (не считая нескольких переменных-счётчиков), независимо от размера входных данных. Альтернатива — сортировка, которой нужна вторая полка целиком: скопировать элементы в новую структуру, отсортировать её и, возможно, скопировать результат обратно. Такой подход требует $O(n)$ дополнительной памяти.

Определение. Алгоритм сортировки называется сортировкой на месте, если объём дополнительной (вспомогательной) памяти, которую он использует помимо самого входного массива, есть $O(1)$ — то есть не растёт с увеличением размера входных данных.

Примеры с разбором

Пример 1. Учёт памяти для всех трёх алгоритмов урока. Во всех приведённых выше реализациях selection_sort, bubble_sort и insertion_sort дополнительная память — это буквально несколько переменных: счётчики i, j, временная переменная при обмене (или key при вставке). Ни один из них не создаёт нового массива или списка. Формально это записывается как $O(1)$ дополнительной памяти — все три алгоритма урока сортируют на месте.

def swap_in_place(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]   # кортеж (arr[j], arr[i]) создаётся,
    # но его размер константный (2 элемента) и не зависит от n —
    # это не нарушает свойство "на месте"

Пример 2. Не-in-place вариант той же идеи. Возьмём алгоритм, концептуально похожий на сортировку выбором, но реализованный через построение нового списка:

def selection_sort_extra_memory(arr):
    remaining = list(arr)   # копия — уже O(n) дополнительной памяти
    sorted_list = []        # ещё один список — тоже растёт до O(n)
    while remaining:
        m = min(remaining)
        remaining.remove(m)
        sorted_list.append(m)
    return sorted_list

Трассировка на массиве $[3, 1, 2]$:

remaining=[3,1,2], sorted_list=[]
  минимум 1 -> remaining=[3,2], sorted_list=[1]
  минимум 2 -> remaining=[3],   sorted_list=[1,2]
  минимум 3 -> remaining=[],    sorted_list=[1,2,3]

Алгоритмически это почти то же самое, что сортировка выбором, но реализация тратит память на две дополнительные структуры, суммарно занимающие $O(n)$, вместо того чтобы переставлять элементы прямо внутри исходного массива. Это уже не сортировка на месте, хотя асимптотика по времени та же — $O(n^2)$.

Пример 3. Практическое различие: list.sort() против sorted() в Python.

data = [5, 3, 1, 4, 2]

data.sort()             # сортирует "на месте", возвращает None,
                         # дополнительной памяти на копию массива не тратится

new_data = sorted(data)  # создаёт и возвращает НОВЫЙ отсортированный список,
                          # требует O(n) дополнительной памяти на копию

Для массива из пяти чисел разница незаметна, но при сортировке гигантского массива, который сам по себе занимает почти весь доступный объём оперативной памяти (например, обработка большого датасета на сервере с жёстким лимитом по памяти), выбор между list.sort() и sorted() может решить, поместится ли операция в память вообще или процесс упадёт с ошибкой нехватки памяти.

Почему это важно

В условиях ограниченной памяти — встраиваемые системы, обработка данных, которые сами по себе занимают почти весь доступный объём ОЗУ, сортировка «на лету» больших потоков — свойство «на месте» может быть решающим фактором выбора алгоритма, даже ценой худшей асимптотики по времени. Важно сразу зафиксировать связку понятий, которая пригодится в следующих двух уроках: быстрая сортировка (урок 267) — тоже фактически сортировка на месте (не считая $O(\log n)$ памяти на стек рекурсии), а вот сортировка слиянием (урок 268), несмотря на гарантированную сложность $O(n \log n)$ в любом случае, платит за эту гарантию необходимостью в $O(n)$ дополнительной памяти на вспомогательный массив при слиянии. Ни один из подходов не является «правильным» универсально — выбор всегда зависит от того, чем ты готов пожертвовать: временем, памятью или устойчивостью.

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

Алгоритм	Лучший случай	Средний случай	Худший случай	Память	Устойчив	На месте
Сортировка пузырьком	$O(n)$ (с ранним выходом)	$O(n^2)$	$O(n^2)$	$O(1)$	да	да
Сортировка вставками	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	да	да
Сортировка выбором	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	нет (в стандартной реализации)	да

Несколько выводов из этой таблицы, которые легко упустить, если смотреть только на «класс сложности»:

Все три алгоритма имеют одинаковый худший случай $O(n^2)$, но заметно различаются по лучшему случаю — сортировка выбором не выигрывает вообще ничего от удачного порядка входных данных, а пузырьковая и вставочная сортировки на почти отсортированных данных приближаются к линейному времени.
Сортировка выбором делает меньше всего обменов (не более $n-1$), но не меньше всего сравнений — по сравнениям она столь же затратна, как худший случай двух других.
Устойчивость — это не «бонус», который есть у всех алгоритмов сортировки автоматически: конкретно сортировка выбором в её типичной формулировке эту гарантию не даёт, хотя её можно сделать устойчивой ценой замены обмена на сдвиг (тогда она перестанет быть настолько экономной по записям).
На практике при выборе между тремя алгоритмами для небольшого массива стоит по умолчанию выбирать сортировку вставками: она устойчива, адаптивна к почти упорядоченным данным и обычно быстрее двух других по фактическому числу операций, несмотря на одинаковый класс сложности.

Когда квадратичные алгоритмы всё ещё оправданы

Может показаться, что раз в следующих двух уроках появятся алгоритмы с гарантией $O(n \log n)$, квадратичные алгоритмы можно спокойно забыть. Это не так, и вот конкретные причины, почему инженеры продолжают сознательно использовать их даже в 2026 году.

Маленькие массивы. У более сложных алгоритмов вроде быстрой сортировки и сортировки слиянием есть накладные расходы — рекурсивные вызовы, дополнительные проверки условий, иногда выделение памяти. Для очень маленьких $n$ (порядка $10$–$20$ элементов) эти константные издержки могут превышать выигрыш от лучшей асимптотики: $O(n \log n)$ с большой константой на крошечном $n$ вполне может оказаться медленнее, чем $O(n^2)$ с маленькой константой. Именно поэтому реализация std::sort в стандартной библиотеке C++ и многие реализации быстрой сортировки переключаются на вставочную сортировку, когда рекурсивный подмассив становится меньше определённого порога (обычно между $10$ и $20$ элементами).

Почти отсортированные данные. Реальные данные редко бывают перемешаны полностью случайно. Логи с временными метками, инкрементально дополняемые списки, потоковые данные, которые почти упорядочены и лишь изредка получают элемент «не в том месте», — во всех этих случаях сортировка вставками с её адаптивной сложностью, близкой к $O(n)$, оказывается конкурентоспособной или даже превосходит формально более быстрые алгоритмы, у которых нет механизма распознать «почти готовый» массив.

Ограниченная память и простота реализации. Во встраиваемых системах, микроконтроллерах или в коде, который должен быть предельно надёжным и простым для аудита (например, в критически важных системах), простота и предсказуемость сортировки вставками — реальное инженерное преимущество перед более быстрым, но и более сложным для верификации алгоритмом.

Как «базовый случай» внутри гибридных алгоритмов. Это, пожалуй, самая распространённая причина, по которой квадратичные алгоритмы живут в промышленном коде прямо сейчас: Timsort использует вставочную сортировку для коротких прогонов, а большинство промышленных реализаций быстрой сортировки переключаются на неё же для маленьких подмассивов в процессе рекурсии. Формально такие гибридные алгоритмы всё равно называют «$O(n \log n)$», но их реальная скорость на практике во многом обязана именно грамотному использованию простой квадратичной сортировки там, где она эффективнее.

Практика: 30 заданий

Базовый уровень (задания 1–10)

Задание 1. Выполни полную трассировку сортировки выбором для массива $[7, 2, 9, 4]$: покажи состояние массива после каждой итерации $i$.

Задание 2. Для массива $[5, 1, 4, 2]$ выполни один проход (первую итерацию $i$) сортировки пузырьком. Покажи массив после каждого сравнения соседней пары.

Задание 3. Выполни первые три шага (индексы $i=1,2,3$) сортировки вставками для массива $[9, 5, 1, 4, 3]$.

Задание 4. Является ли сортировка пузырьком (в стандартной реализации со строгим сравнением $A[j] > A[j+1]$) устойчивой? Обоснуй ответ, не приводя числового примера, а рассуждая об устройстве алгоритма.

Задание 5. Сколько сравнений выполнит сортировка выбором для массива из $n=6$ элементов, независимо от их порядка? Выведи формулу.

Задание 6. Сколько сравнений выполнит оптимизированная сортировка пузырьком (с флагом раннего выхода) на уже отсортированном массиве из $5$ элементов?

Задание 7. Сколько сравнений в лучшем случае выполнит сортировка вставками для уже отсортированного массива из $6$ элементов?

Задание 8. Использует ли сортировка выбором в приведённой в уроке реализации дополнительную память, растущую с размером входного массива? Обоснуй.

Задание 9. Построй собственный пример массива из трёх пар (значение, метка) с двумя равными значениями, на котором сортировка выбором нарушает устойчивость. Покажи трассировку.

Задание 10. Массив из $n=10$ элементов полностью перемешан. Сравни максимально возможное число обменов для сортировки выбором и для сортировки пузырьком (без оптимизации раннего выхода). Почему сортировка выбором предпочтительнее, если операция записи дорогая?

Средний уровень (задания 11–20)

Задание 11. Модифицируй код сортировки пузырьком из урока так, чтобы она сортировала массив по убыванию, и протрассируй её на $[3, 1, 4, 1, 5]$ (первый проход).

Задание 12. Посчитай точное число сдвигов, которое сделает сортировка вставками для массива, отсортированного строго в обратном порядке: $[4, 3, 2, 1]$.

Задание 13. Реализуй вариант сортировки выбором, который на каждом шаге ищет не минимум, а максимум, и строит отсортированный массив с конца. Протрассируй на $[6, 2, 9, 1]$.

Задание 14. Для массива пар $[(4,\text{'a'}), (2,\text{'b'}), (4,\text{'c'}), (2,\text{'d'})]$ протрассируй сортировку вставками и подтверди её устойчивость.

Задание 15. Сколько всего сравнений выполнит сортировка пузырьком без оптимизации раннего выхода для массива из $n=100$ уже отсортированных элементов? А с оптимизацией? Во сколько раз оптимизация экономит сравнения в этом случае?

Задание 16. У тебя есть таблица сотрудников с колонками «отдел» и «зарплата». Опиши по шагам (без кода), в каком порядке нужно применить два устойчивых прохода сортировки, чтобы получить таблицу, сгруппированную по отделам, где внутри каждого отдела зарплаты идут по убыванию.

Задание 17. Алгоритм построения дерева решений ищет лучший порог разбиения по числовому признаку, для чего сортирует все $n$ значений этого признака. Если в дереве $d$ уровней и на каждом уровне узел заново сортирует свою часть данных, какова грубая оценка суммарной стоимости сортировок по всему дереву, если использовать сортировку выбором (или любую другую $O(n^2)$)?

Задание 18. Чтобы найти $3$ наименьших расстояния среди $10$ точек для метода k ближайших соседей, можно применить «частичную» сортировку выбором: выполнять только первые $k$ итераций внешнего цикла вместо всех $n-1$. Посчитай, сколько сравнений это потребует, и сравни с полной сортировкой всех $10$ элементов.

Задание 19. Для массива $[3, 1, 2]$ посчитай число инверсий (пар индексов $i A[j]$) и сравни его с числом сдвигов, которое выполнит сортировка вставками на этом массиве.

Задание 20. Опиши, как модифицировать сортировку выбором, чтобы она стала устойчивой, ценой замены обмена на сдвиг (аналогично сортировке вставками). Сохранится ли при этом свойство «сортировка на месте»?

Продвинутый уровень (задания 21–30)

Задание 21. Докажи формально, что сортировка пузырьком с флагом раннего выхода устойчива, и выведи её точные асимптотики для лучшего и худшего случаев по числу сравнений.

Задание 22. Докажи, что сортировка выбором для массива из $n$ элементов выполняет не более $n-1$ обменов, независимо от входных данных, и объясни, почему это делает её привлекательной, когда стоимость записи много выше стоимости сравнения (например, при сортировке строк базы данных на флеш-накопителе с ограниченным ресурсом перезаписи).

Решение:

Шаг 1. Алгоритм совершает ровно один потенциальный обмен на каждую из $n-1$ итераций внешнего цикла ($i$ от $0$ до $n-2$) — обмен $A[i]$ с найденным минимумом на позициях $i \ldots n-1$.

Шаг 2. Если минимум уже находится на позиции $i$ (то есть min_idx == i), реальный обмен можно пропустить (как в реализации урока), поэтому фактическое число обменов не превышает $n-1$, а может быть и меньше.

Шаг 3. Ни при каком порядке входных данных число итераций внешнего цикла не меняется — значит, верхняя граница $n-1$ обменов гарантирована всегда, в отличие, например, от сортировки пузырьком, где число обменов зависит от степени перемешанности входа и может достигать $\dfrac{n(n-1)}{2}$.

Шаг 4. Если каждая запись (обмен) на носителе стоит значительно дороже, чем сравнение в оперативной памяти (например, из-за ограниченного числа циклов перезаписи флеш-памяти или задержки записи на диск), минимизация именно числа записей — более важный критерий, чем минимизация числа сравнений, и здесь сортировка выбором гарантированно выигрывает у сортировки пузырьком.

Ответ: не более $n-1$ обменов при любых входных данных — это доказывается прямо из структуры внешнего цикла; при дорогой записи это делает сортировку выбором осознанным инженерным выбором, а не просто учебным примером

Задание 23. Выведи ожидаемое (среднее) число сдвигов сортировки вставками для случайной перестановки из $n$ элементов, используя связь со средним числом инверсий в случайной перестановке.

Задание 24. Сортировка пузырьком и сортировка вставками относятся к одному классу сложности $O(n^2)$ и обе устойчивы, но на практике вставочная сортировка используется в промышленном коде, а пузырьковая — почти никогда. Приведи не менее двух содержательных причин этого различия, помимо самого класса сложности.

Решение:

Шаг 1 (число операций записи). Сортировка пузырьком совершает обмен при каждом обнаруженном нарушении порядка соседней пары, и таких обменов может быть до $\dfrac{n(n-1)}{2}$. Сортировка вставками для того же худшего случая делает сопоставимое число сдвигов, но один обмен в пузырьковой сортировке обычно реализуется как три присваивания (через временную переменную) или эквивалент, тогда как последовательные сдвиги в цикле сортировки вставками дешевле на практике из-за более простого шаблона доступа к памяти.

Шаг 2 (локальность обращений к памяти). Сортировка вставками обращается к уже частично упорядоченному, компактному диапазону памяти при сдвиге элементов, что хорошо согласуется с кэшированием процессора. Сортировка пузырьком многократно проходит по всему рабочему диапазону на каждой итерации, из-за чего в реальных измерениях (не только в теоретической оценке числа операций) она обычно оказывается медленнее вставочной сортировки при сопоставимом числе сравнений.

Шаг 3 (адаптивность на практике). Хотя обе имеют лучший случай $O(n)$ на отсортированных данных при наличии соответствующей оптимизации, вставочная сортировка ведёт себя предсказуемо лучше на почти (не идеально) отсортированных данных — типичном случае в реальных задачах, — тогда как выигрыш от раннего выхода в пузырьковой сортировке требует, чтобы весь проход целиком не нашёл ни единого нарушения.

Ответ: несмотря на одинаковый формальный класс сложности, вставочная сортировка обычно выигрывает по фактическому числу операций записи, по дружественности к кэшу процессора и по устойчивой адаптивности на реалистично «почти упорядоченных» данных — поэтому именно она, а не пузырьковая сортировка, используется как базовый случай внутри промышленных гибридных алгоритмов вроде Timsort

Задание 25. Есть список задач с полями (приоритет, время создания), и нужно получить порядок: сначала по приоритету по убыванию, а при равном приоритете — по времени создания по возрастанию. Опиши два эквивалентных способа получить такой порядок: через составной ключ сортировки и через два последовательных устойчивых прохода. Докажи, что оба способа дают одинаковый результат.

Решение:

Шаг 1 (составной ключ). Можно отсортировать список один раз, используя ключ-кортеж $(-\text{приоритет}, \text{время создания})$ — знак минус превращает сортировку по убыванию приоритета в сортировку по возрастанию отрицательного значения, а лексикографическое сравнение кортежей автоматически учитывает время создания как «тай-брейк» при равенстве первых компонентов.

Шаг 2 (два прохода). Альтернативно: сначала устойчиво отсортировать по времени создания по возрастанию (второстепенный ключ), а затем устойчиво отсортировать результат по приоритету по убыванию (главный ключ) — устойчивость второго прохода гарантирует, что внутри каждой группы одинакового приоритета сохранится порядок по времени, заданный первым проходом.

Шаг 3 (эквивалентность). Оба способа реализуют одно и то же математическое отношение порядка: «сравнивай сначала по приоритету, при равенстве — по времени». Составной ключ делает это явно за один проход сравнения кортежей; два последовательных устойчивых прохода добиваются того же результата неявно, полагаясь на определение устойчивости. Формально: для любых двух элементов с разным приоритетом оба способа расположат их в одном и том же порядке по приоритету; для любых двух элементов с одинаковым приоритетом оба способа расположат их по времени создания — значит, итоговые перестановки совпадают.

Ответ: оба подхода эквивалентны; составной ключ — более компактный способ выразить многоуровневый порядок за один проход, а связка из двух устойчивых сортировок — более общий приём, применимый и тогда, когда API сортировки не поддерживает составные ключи напрямую (например, при последовательных вызовах ORDER BY в разных запросах или ручной реализации многоуровневой сортировки)

Задание 26. Датасет содержит $10\,000$ строк и $20$ признаков. Алгоритм построения дерева решений на каждом узле сортирует значения каждого признака заново, чтобы найти лучший порог разбиения, используя сортировку с $O(n \log n)$ (тема следующих уроков). Оцени, почему предварительная однократная сортировка всех признаков перед построением дерева обычно выгоднее, чем пересортировка на каждом узле, и сформулируй условие, когда это не так.

Решение:

Шаг 1. При пересортировке на каждом узле суммарная стоимость сортировок по всему дереву глубины $d$ составляет порядка $O(d \cdot n \log n \cdot p)$, где $p=20$ — число признаков, потому что каждый уровень дерева заново тратит $O(n \log n)$ на каждый признак, даже если данные на этом уровне уже частично упорядочены с предыдущего шага.

Шаг 2. При однократной предварительной сортировке всех признаков (один раз, $O(p \cdot n \log n)$ суммарно) и последующем поддержании этого порядка через индексы при разбиении узлов (а не пересортировке значений заново) стоимость сортировки не умножается на глубину дерева — она оплачивается один раз в начале.

Шаг 3. Разница особенно заметна при большой глубине дерева $d$: без предварительной сортировки множитель $d$ делает построение дерева существенно дороже. Реальные промышленные реализации (например, в градиентном бустинге) действительно сортируют значения признаков один раз и переиспользуют этот порядок при разбиении узлов.

Шаг 4. Условие, когда пересортировка на каждом узле может быть оправдана — если данные внутри узла настолько малы (маленькие листовые узлы у самого низа дерева) и почти отсортированы, что дешёвый адаптивный алгоритм вроде сортировки вставками на них практически бесплатен, а поддержание сложной структуры индексов между уровнями создаёт больше накладных расходов, чем экономит.

Ответ: предварительная однократная сортировка признаков обычно выгоднее, потому что она убирает множитель глубины дерева $d$ из общей стоимости; пересортировка на каждом узле оправдана лишь при очень маленьких, почти упорядоченных подмножествах данных, где накладные расходы на поддержание индексов порядка превышают стоимость дешёвой локальной пересортировки

Задание 27. Дай формальное определение «адаптивного алгоритма сортировки» через число инверсий входного массива и классифицируй сортировку пузырьком (с ранним выходом), сортировку вставками и сортировку выбором по этому критерию, обосновав каждый случай.

Решение:

Шаг 1 (определение). Алгоритм сортировки называется адаптивным, если его время работы есть функция не только от размера входа $n$, но и от степени «беспорядка» во входных данных — как правило, измеряемого числом инверсий $I$ — так, что при малом $I$ (данные почти отсортированы) время работы существенно меньше, чем в худшем случае, например $O(n+I)$.

Шаг 2 (сортировка вставками). Как показано в заданиях 19 и 23, общее число сдвигов в точности равно числу инверсий $I$, а число сравнений отличается от него не более чем на линейное слагаемое — время работы $O(n+I)$. Это классический пример адаптивного алгоритма.

Шаг 3 (сортировка пузырьком с ранним выходом). Число проходов до полной сортировки связано с «расстоянием», на которое нужно переместить самый смещённый элемент, а ранний выход экономит проходы, если беспорядка мало. Формально доказывается, что и она адаптивна по числу инверсий, хотя константы обычно хуже, чем у вставочной сортировки.

Шаг 4 (сортировка выбором). Как показано в примере 2 раздела про сортировку выбором, число сравнений всегда равно $\dfrac{n(n-1)}{2}$ независимо от входа — время работы никак не зависит от числа инверсий. Это неадаптивный алгоритм.

Ответ: сортировка вставками и сортировка пузырьком (с ранним выходом) — адаптивные алгоритмы, их производительность улучшается на почти упорядоченных данных; сортировка выбором — неадаптивна, её время работы константно относительно степени беспорядка входа

Задание 28. Для сортировки вставками построй худший возможный вход размера $n=5$ (массив, дающий максимальное число сравнений и сдвигов), выполни полную трассировку и подтверди, что итоговое число сравнений равно $\dfrac{n(n-1)}{2}$.

Задание 29. Для массива $[9, 7, 5, 3, 1]$ (строго убывающий, $n=5$) определи, какой из трёх алгоритмов урока выполнит наименьшее число операций записи (обменов или сдвигов), и приведи точные числа для всех трёх.

Задание 30. Опиши гибридную стратегию сортировки, которая использует сортировку вставками для подмассивов размером менее $16$ элементов и более быстрый алгоритм (например, из следующих уроков) для всех остальных случаев. Почему такая стратегия обычно быстрее, чем использование быстрого алгоритма для всех размеров без исключения?

Решение:

Шаг 1 (стратегия). Основной алгоритм рекурсивно делит массив на всё меньшие части (как это делают быстрая сортировка и сортировка слиянием из следующих уроков). Как только размер обрабатываемого подмассива становится меньше порога (например, $16$ элементов), рекурсия прерывается, и этот маленький подмассив сортируется напрямую сортировкой вставками вместо дальнейшего рекурсивного деления.

Шаг 2 (почему это быстрее). У более сложных алгоритмов есть накладные расходы на каждый рекурсивный вызов — передачу границ подмассива, возможное выделение памяти, дополнительные проверки условий. Для очень маленьких подмассивов эти издержки составляют существенную (иногда доминирующую) долю времени выполнения, тогда как сортировка вставками для $15$-$16$ элементов выполняется буквально за десятки операций без какой-либо рекурсии.

Шаг 3 (связь с реальными библиотеками). Именно эту стратегию используют std::sort в C++ и большинство промышленных реализаций быстрой сортировки — экспериментально подобранный порог (обычно между $10$ и $20$) даёт заметное ускорение по сравнению с «чистой» рекурсией до подмассивов из одного элемента, потому что убирает лишние уровни рекурсии там, где выигрыш от асимптотики $O(n \log n)$ ещё не успевает перевесить константные издержки.

Ответ: гибридная стратегия «сложный алгоритм для больших подмассивов плюс сортировка вставками для маленьких» быстрее чистого рекурсивного подхода, потому что убирает накладные расходы рекурсии там, где они не окупаются выигрышем в асимптотике — это подтверждённый практикой приём, встроенный в стандартные библиотеки большинства языков программирования

Частые ошибки

❌ Ошибка: Считать, что все три квадратичных алгоритма сортировки одинаково хороши или одинаково бесполезны, раз у них общий класс сложности $O(n^2)$.

✅ Правильно: У алгоритмов с одинаковым худшим случаем могут кардинально различаться лучший случай, число операций записи, устойчивость и практическая скорость.

💡 Почему: Асимптотика описывает только порядок роста при больших $n$ и не учитывает константы, адаптивность к структуре входных данных и поведение при обращении к памяти — все три фактора решают исход дела на практике.

❌ Ошибка: Считать сортировку выбором устойчивой, потому что она «просто расставляет элементы по местам».

✅ Правильно: Сортировка выбором в стандартной реализации через обмен неустойчива — обмен местами двух не соседних элементов может нарушить относительный порядок равных элементов между ними.

💡 Почему: Устойчивость определяется конкретным механизмом перестановки, а не общей идеей алгоритма — замена обмена на сдвиг сделала бы сортировку выбором устойчивой, но такой она не является в своём типичном виде.

❌ Ошибка: Путать «сортировку на месте» с «сортировкой без единой дополнительной переменной».

✅ Правильно: In-place означает $O(1)$ дополнительной памяти — то есть память, не зависящую от $n$; несколько переменных-счётчиков или временная переменная при обмене не нарушают это свойство.

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

❌ Ошибка: Полагать, что раз современные библиотеки используют быстрые алгоритмы $O(n \log n)$, то простые квадратичные алгоритмы больше нигде не встречаются в реальном коде.

✅ Правильно: Вставочная сортировка живёт внутри практически каждой промышленной реализации сортировки — как базовый случай для маленьких подмассивов и коротких прогонов в гибридных схемах вроде Timsort.

💡 Почему: Гибридные стратегии выбирают наиболее эффективный алгоритм в зависимости от размера данных, и для маленьких $n$ этим наиболее эффективным алгоритмом часто оказывается именно квадратичный.

❌ Ошибка: Считать число сравнений и число операций записи (обменов, сдвигов) взаимозаменяемыми метриками эффективности алгоритма.

✅ Правильно: Это две разные величины, которые могут расти с разной скоростью относительно друг друга — сортировка выбором минимизирует записи, но не сравнения; выбор метрики должен зависеть от того, что на конкретном оборудовании дороже.

💡 Почему: На разных типах памяти (оперативная память, диск, флеш-накопитель с ограниченным ресурсом перезаписи) соотношение стоимости сравнения и записи сильно различается, и оптимальный алгоритм для одного оборудования может быть не оптимален для другого.

❌ Ошибка: Думать, что «адаптивность» алгоритма сортировки — это про удобство использования или простоту кода.

✅ Правильно: Адаптивность — строго определённое свойство: время работы алгоритма явно зависит от степени упорядоченности (числа инверсий) входных данных, а не только от их размера.

💡 Почему: Без точного определения легко спутать «алгоритм простой в реализации» с «алгоритм эффективен на почти отсортированных данных» — это совершенно независимые характеристики.

Главное запомнить

✅ Сортировка выбором: на каждом шаге находит минимум в необработанной части и ставит его на место; всегда $\Theta(n^2)$ сравнений независимо от входа (неадаптивна), но не более $n-1$ обменов; неустойчива в стандартной реализации

✅ Сортировка пузырьком: сравнивает и меняет местами соседние элементы; с флагом раннего выхода — лучший случай $O(n)$ на отсортированных данных, устойчива, но на практике почти не используется из-за большого числа обменов

✅ Сортировка вставками: строит отсортированную часть постепенно, вставляя очередной элемент на нужное место; адаптивна (лучший случай $O(n)$, среднее число сдвигов равно $n(n-1)/4$), устойчива, и единственная из трёх реально применяется в промышленном коде как базовый случай гибридных алгоритмов

✅ Устойчивость — свойство сохранять относительный порядок элементов с равными ключами; именно на нём строится многоуровневая сортировка данных по нескольким столбцам, например DataFrame.sort_values(by=[...]) в pandas

✅ Многоуровневую сортировку без составного ключа можно получить через последовательность устойчивых сортировок от второстепенного ключа к главному

✅ Сортировка на месте (in-place) означает $O(1)$ дополнительной памяти сверх входного массива; все три алгоритма урока сортируют на месте

✅ Число сдвигов сортировки вставками на любом входе в точности равно числу инверсий этого входа — это связывает алгоритм с формальной мерой «беспорядка» в данных

✅ Квадратичные алгоритмы всё ещё оправданы для маленьких массивов, почти отсортированных данных и как базовый случай внутри гибридных схем вроде Timsort или реализаций быстрой сортировки

✅ Сортировка — не абстрактная задача из учебника, а операция, лежащая в основе поиска порогов разбиения в деревьях решений и поиска ближайших соседей в методе k-NN

✅ Следующие два урока разберут, как алгоритмы «разделяй и властвуй» — быстрая сортировка и сортировка слиянием — добиваются гарантии $O(n \log n)$ там, где три алгоритма этого урока ограничены квадратом

Связь с темами курса

🔙 Откуда пришли: Из урока 265 — минимальное остовное дерево, где алгоритм Крускала уже опирался на предварительную сортировку рёбер по весу; этот урок формализует саму операцию сортировки, которая до сих пор использовалась как готовый строительный блок.

🔜 Куда идём: Следующие два урока целиком посвящены тому, как выйти за пределы $O(n^2)$. Урок 267 разберёт быструю сортировку (QuickSort) — алгоритм «разделяй и властвуй» на основе опорного элемента, дающий $O(n \log n)$ в среднем случае почти на месте по памяти. Урок 268 разберёт сортировку слиянием (Merge Sort) — алгоритм с гарантированным $O(n \log n)$ в любом случае, ценой $O(n)$ дополнительной памяти на слияние. Обрати внимание, что многие идеи этого урока прямо понадобятся там: устойчивость сортировки слиянием (она устойчива по построению) и роль сортировки вставками как базового случая внутри быстрой сортировки для маленьких подмассивов.

🎯 В машинном обучении: Сортировка значений числового признака — стандартный первый шаг при поиске оптимального порога разбиения в деревьях решений (используемых и напрямую, и как базовые модели в случайном лесе и градиентном бустинге); сортировка расстояний до точек запроса — основа наивной реализации метода k ближайших соседей. Понимание разницы между устойчивой и неустойчивой, in-place и не-in-place сортировкой напрямую переносится на повседневную работу с pandas.DataFrame.sort_values, где многоколоночная сортировка и её предсказуемость при равных значениях — не техническая деталь, а вопрос корректности итогового анализа данных.

Интересные факты

📌 Механическая сортировка перфокарт существовала ещё в конце XIX века — табуляционные машины Германа Холлерита для переписи населения США 1890 года могли физически сортировать карточки по пробитым отверстиям, за десятилетия до появления электронных вычислителей и самого термина «алгоритм сортировки» в его современном понимании.

📌 Дональд Кнут посвятил сортировке и поиску целый третий том своей серии «Искусство программирования» (1973), в котором систематизировал десятки вариаций сортировочных алгоритмов и снабдил каждый детальным математическим анализом — том до сих пор остаётся одним из самых авторитетных справочников по теме, спустя более чем полвека после первого издания.

📌 Timsort, алгоритм, встроенный в стандартную сортировку Python с 2002 года и позднее принятый в Java (для сортировки объектов) и Android, был назван в честь своего автора — Тима Питерса. Он представляет собой гибрид сортировки слиянием и сортировки вставками: находит уже упорядоченные «прогоны» в реальных данных (которые редко бывают полностью случайными) и сортирует вставками только короткие неупорядоченные фрагменты.

📌 Сортировка вставками при определённых условиях (данные поступают по одному элементу, порядок должен поддерживаться постоянно) используется не как временное решение «на потом отсортируем», а как единственно правильная стратегия — например, для поддержания отсортированного списка лидеров онлайн-турнира, где после каждого нового результата нужно быстро найти его место среди уже имеющихся, а не пересортировывать весь список заново.

Лайфхаки и полезные трюки

💡 Если нужно быстро прикинуть, сколько сравнений сделает сортировка выбором на массиве заданного размера, не считай по шагам — сразу применяй формулу $\dfrac{n(n-1)}{2}$: это число неизменно для любого входа, в отличие от двух других алгоритмов урока.

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

💡 При отладке собственной реализации любого из трёх алгоритмов полезно написать отдельную функцию-проверку инварианта — например, для сортировки вставками проверять, что после обработки индекса $i$ подмассив $A[0..i]$ действительно отсортирован — и вызывать её на каждой итерации в тестах; это быстро находит ошибки off-by-one в границах циклов.

💡 Если стоит выбор между sorted() и list.sort() в Python (или аналогами в других языках), задай вопрос: нужен ли тебе исходный неотсортированный массив после операции? Если нет — используй сортировку на месте (list.sort()), она экономит память; если да (например, чтобы сравнить порядок «до» и «после») — используй вариант, возвращающий новый массив.

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

💡 Перед тем как писать вручную любой из трёх алгоритмов этого урока в реальном проекте (а не в учебных целях), вспомни: почти для любой прикладной задачи правильный выбор — встроенная функция сортировки языка (sorted(), Array.prototype.sort, std::sort). Она почти наверняка уже реализует нужную гибридную стратегию быстрее и надёжнее, чем самописный код, — три алгоритма этого урока стоит писать своими руками ради понимания механики, а не ради использования в продакшене.

Три алгоритма этого урока — самые простые в курсе, и именно поэтому они лучше всего подходят, чтобы разглядеть, из чего вообще складывается «эффективность» алгоритма: не только из итоговой асимптотики, но из числа сравнений, числа операций записи, устойчивости к равным ключам и требований к памяти. Ты увидел, что сортировка выбором жертвует адаптивностью ради минимума записей, сортировка пузырьком жертвует практической скоростью ради простоты и наглядности, а сортировка вставками почти по всем параметрам оказывается лучшей из трёх — настолько, что реальные библиотеки прячут её внутри куда более сложных схем. Дальше в курсе эта база пригодится буквально сразу: следующие два урока покажут, как идея «разделяй и властвуй» позволяет вырваться из квадратичной сложности и добиться $O(n \log n)$ — сначала через быструю сортировку с её опорным элементом, а затем через сортировку слиянием с её гарантированной устойчивостью и предсказуемой производительностью в любом случае.

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку

💬 Нашёл ошибку или есть вопрос по уроку? Написать в Telegram →