Сортировка выбором

TL;DR

Сортировка выбором (selection sort) делит массив на отсортированный префикс и неотсортированный остаток; на каждом шаге в остатке находится минимум и обменивается с первым элементом остатка. Алгоритм работает на месте ([math]\displaystyle{ O(1) }[/math] памяти), делает не более [math]\displaystyle{ n-1 }[/math] обменов — это его главное достоинство, когда запись дороже сравнения (флеш-память, EEPROM). Но число сравнений всегда [math]\displaystyle{ \frac{n(n-1)}{2} }[/math]: алгоритм не адаптивен (на отсортированном массиве делает столько же сравнений, сколько на обратном) и неустойчив. Поэтому на практике он обычно уступает сортировке вставками (адаптивной и устойчивой) и [math]\displaystyle{ O(n\log n) }[/math]-алгоритмам; его ниша — дорогая запись и простота. Идея «выбрать минимум» живёт в быстром выборе (quickselect), пирамидальной сортировке и турнирном отборе top-[math]\displaystyle{ k }[/math].

Свойство	Значение
Класс	Сортировка сравнением; на месте
Порядок	На каждом шаге минимум — в начало остатка
Сравнений	всегда [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] (не адаптивна)
Обменов	[math]\displaystyle{ \le n-1 }[/math]
Записей	[math]\displaystyle{ \le 2(n-1) }[/math] (обмен — 2 записи)
Лучший / средний / худший	все [math]\displaystyle{ \Theta(n^2) }[/math]
Память	[math]\displaystyle{ O(1) }[/math]
Устойчивость	нет
Сильная сторона	минимум записей (обменов)
Варианты	двусторонняя (min+max), на списке, k-выбор
Родственники	heapsort (выбор с кучей), quickselect
Где встречается	флеш/EEPROM, embedded, обучение, отбор top-k

Определения

Сортировка выбором — алгоритм, который для каждого [math]\displaystyle{ i }[/math] (от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ n-2 }[/math]) находит индекс минимума в [math]\displaystyle{ a[i..n-1] }[/math] и, если индекс не совпадает с [math]\displaystyle{ i }[/math], обменивает его с [math]\displaystyle{ a[i] }[/math]. После шага [math]\displaystyle{ i }[/math] префикс [math]\displaystyle{ a[0..i] }[/math] отсортирован.

Задача выбора (selection problem) — найти [math]\displaystyle{ k }[/math]-й по порядку элемент (или [math]\displaystyle{ k }[/math] наименьших). Это обобщение шага сортировки выбором; решается за [math]\displaystyle{ O(n) }[/math] в среднем (quickselect) или [math]\displaystyle{ O(n\log k) }[/math] для [math]\displaystyle{ k }[/math] наименьших (куча/турнир).

На месте (in-place) — [math]\displaystyle{ O(1) }[/math] дополнительной памяти: одна переменная под индекс минимума и обмен.

Неадаптивность — число сравнений не зависит от исходного порядка: всегда [math]\displaystyle{ \frac{n(n-1)}{2} }[/math].

Неустойчивость — обмен далёкого минимума с ближним элементом может изменить взаимный порядок равных ключей.

Обмен (swap) — операция, меняющая два элемента местами; в модели «дорогой записи» считается основной стоимостью (в обмене участвуют 2 чтения и 2 записи).

Обозначения. [math]\displaystyle{ n }[/math] — длина массива; [math]\displaystyle{ i }[/math] — граница отсортированного префикса; [math]\displaystyle{ mn }[/math] — индекс минимума; [math]\displaystyle{ H_n }[/math] — [math]\displaystyle{ n }[/math]-е гармоническое число; [math]\displaystyle{ \log }[/math] — двоичный.

Мотивация и интуиция

Основной ресурс, который экономит сортировка выбором, — записи (обмены). Она делает их [math]\displaystyle{ O(n) }[/math] вместо [math]\displaystyle{ O(n^2) }[/math]. В большинстве сред (RAM) запись дешева, и вставки/quicksort быстрее. Но когда запись в энергонезависимую память дорога и изнашивает ячейки (флеш, EEPROM), число записей становится главным критерием — и тогда сортировка выбором привлекательна (см. рис. 2).

Идея в одном абзаце: найти минимум в остатке и поставить его в начало. Мы платим за это полным перебором остатка на каждом шаге ([math]\displaystyle{ \frac{n(n-1)}{2} }[/math] сравнений), но зато помещаем элемент на место одним обменом, а не множеством сдвигов. Отсюда компромисс «меньше записей — больше сравнений».

Рис. 1. Сортировка выбором: минимум остатка меняется с первым элементом, отсортированный префикс растёт.

Рис. 2. Выбором делает не более [math]\displaystyle{ n-1 }[/math] обменов, но всегда [math]\displaystyle{ n(n-1)/2 }[/math] сравнений — компромисс «меньше записей, больше сравнений».

Устройство

Структура проста: на каждом шаге один проход по остатку ищет минимум, затем — один обмен. Граница отсортированного префикса сдвигается вправо (см. рис. 1 и рис. 3).

Рис. 3. Трассировка [math]\displaystyle{ [6,2,8,5,1,3] }[/math]: два обмена (6↔1 и 8↔3), 15 сравнений.

В отличие от вставок, которые «пристраивают» очередной элемент в префикс, выбором «достаёт» минимум из остатка. Вставки адаптивны и устойчивы, выбором — нет, но у сортировки выбором почти нет перемещений: до [math]\displaystyle{ n-1 }[/math] обменов, то есть до [math]\displaystyle{ 2(n-1) }[/math] записей. Дополнительное следствие: сортировка выбором укладывается в модель «дорогая запись», когда обмен стоит два чтения и две записи, а сравнения дёшевы; выигрыш в том, что записей [math]\displaystyle{ O(n) }[/math], а не [math]\displaystyle{ O(n^2) }[/math], как у вставок. Утверждение «ровно [math]\displaystyle{ n }[/math] записей» относится к циклической сортировке (cycle sort), а не к сортировке выбором.

Граница между «дорого сравнить» и «дорого записать» определяет выбор между вставками (дёшево на почти отсортированных, но много сдвигов) и выбором (мало записей, но всегда полный перебор остатка). Для больших [math]\displaystyle{ n }[/math] обе проигрывают алгоритмам, устраняющим квадратичное число сравнений — heapsort и quicksort.

Операции и алгоритмы

Операция: Selection-Sort

Идея. Для каждого [math]\displaystyle{ i }[/math] найти минимум в [math]\displaystyle{ a[i..n-1] }[/math] и обменять с [math]\displaystyle{ a[i] }[/math].

Пошаговое описание:

1. Для [math]\displaystyle{ i }[/math] от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ n-2 }[/math]: mn ← i.
2. Для [math]\displaystyle{ j }[/math] от [math]\displaystyle{ i+1 }[/math] до [math]\displaystyle{ n-1 }[/math]: если a[j] < a[mn], то mn ← j.
3. Если mn ≠ i, обменять a[i] и a[mn].

Инвариант. Перед шагом [math]\displaystyle{ i }[/math] префикс [math]\displaystyle{ a[0..i-1] }[/math] содержит [math]\displaystyle{ i }[/math] наименьших элементов массива в отсортированном порядке; в [math]\displaystyle{ a[i..n-1] }[/math] — остальные.

Алгоритм Selection-Sort(a)
Вход:  массив a[0..n−1]
Выход: a отсортирован по неубыванию
Инвариант: a[0..i−1] — i наименьших элементов, отсортированы

1  for i ← 0 to n − 2
2      mn ← i
3      for j ← i + 1 to n − 1
4          if a[j] < a[mn]
5              mn ← j
6      if mn ≠ i
7          swap(a[i], a[mn])

Сложность: ровно n(n−1)/2 сравнений; ≤ n−1 обменов; O(1) памяти
Корректность: инвариант сохраняется на каждом шаге; при i = n−1 отсортирован весь массив

Разбор. [6,2,8,5,1,3] (см. рис. 3): шаг 0 — минимум 1 (поз. 4), обмен с 6 → [1,2,8,5,6,3]; шаг 1 — минимум 2 уже на месте; шаг 2 — минимум 3 (поз. 5), обмен с 8 → [1,2,3,5,6,8]; шаги 3 и 4 — без обменов. Всего 2 обмена и 15 сравнений.

Сложность. Сравнений ровно [math]\displaystyle{ \frac{n(n-1)}{2} }[/math]; обменов [math]\displaystyle{ \le n-1 }[/math]; память [math]\displaystyle{ O(1) }[/math].

Крайние случаи. Отсортированный и обратный массивы дают одинаковое число сравнений (не адаптивна). [math]\displaystyle{ n \le 1 }[/math] — ничего.

Операция: двусторонняя сортировка выбором

Идея. За один проход находить и минимум, и максимум остатка; минимум ставить в начало, максимум — в конец (см. рис. 4). Проходов вдвое меньше, но сравнений на каждом проходе вдвое больше.

Пошаговое описание:

1. lo ← 0, hi ← n − 1.
2. Пока lo < hi: пройти по a[lo..hi] и найти индексы минимума mn и максимума mx.
3. Обменять a[lo] с a[mn]; если mx = lo, максимум уехал в позицию mn, поэтому mx ← mn.
4. Обменять a[hi] с a[mx].
5. lo ← lo + 1, hi ← hi − 1; повторять, пока lo < hi.

Инвариант. Перед проходом [math]\displaystyle{ a[0..lo-1] }[/math] — [math]\displaystyle{ lo }[/math] наименьших элементов в порядке возрастания, [math]\displaystyle{ a[hi+1..n-1] }[/math] — [math]\displaystyle{ n-1-hi }[/math] наибольших в порядке возрастания, а в [math]\displaystyle{ a[lo..hi] }[/math] — остальные элементы.

Алгоритм Double-Selection-Sort(a)
Вход:  массив a[0..n−1]
Выход: a отсортирован по неубыванию
Инвариант: a[0..lo−1] — lo наименьших, a[hi+1..n−1] — n−1−hi наибольших, обе части отсортированы

1  lo ← 0 ; hi ← n − 1
2  while lo < hi
3      mn ← lo ; mx ← lo
4      for j ← lo to hi
5          if a[j] < a[mn]
6              mn ← j
7          if a[j] > a[mx]
8              mx ← j
9      if mn ≠ lo
10         swap(a[lo], a[mn])
11     if mx = lo                  # максимум мог уехать в позицию mn
12         mx ← mn
13     if mx ≠ hi
14         swap(a[hi], a[mx])
15     lo ← lo + 1 ; hi ← hi − 1

Сложность: два сравнения на элемент остатка — n(n+2)/2 для чётного n (при n = 6 — 24), Θ(n²) в целом; до двух обменов за проход, всего O(n) (до n); O(1) памяти
Корректность: после прохода lo наименьших и n−1−hi наибольших стоят на своих местах; строка 11 исправляет индекс максимума после первого обмена

Разбор. [6,2,9,5,1,3]: минимум 1 (поз. 4), максимум 9 (поз. 2). Первый обмен — a[0] с a[4]: [1,2,9,5,6,3]. Максимум стоит на поз. 2, поэтому второй обмен — a[5] с a[2]: [1,2,3,5,6,9]. Остаток a[1..4] уже отсортирован, следующие проходы обменов не делают.

Если максимум стоит на lo (например, [9,2,5]), после первого обмена он оказывается на позиции mn: [2,9,5]; строка 11 переставляет mx с lo на mn, после чего второй обмен даёт [2,5,9].

Сложность. В псевдокоде на каждый элемент остатка приходится два сравнения (< mn и > mx), поэтому для чётного [math]\displaystyle{ n }[/math] сравнений [math]\displaystyle{ n(n+2)/2 }[/math] — при [math]\displaystyle{ n = 6 }[/math] это 24, больше, чем 15 у обычной сортировки выбором. Асимптотика остаётся [math]\displaystyle{ \Theta(n^2) }[/math] — это не [math]\displaystyle{ n(n-1)/2 }[/math]. Обменов до двух за проход, всего [math]\displaystyle{ O(n) }[/math] (до [math]\displaystyle{ n }[/math]), память [math]\displaystyle{ O(1) }[/math]. Выигрыш — вдвое меньше проходов, а не меньше сравнений.

Крайние случаи. [math]\displaystyle{ n \le 1 }[/math] — цикл не выполняется. Все элементы равны — значения не меняются, но обмены могут выполняться: mx = lo переводится в mn, и второй обмен формально происходит; на число сравнений это не влияет. Тонкости строк 9–14: если максимум стоял на lo, после первого обмена его индекс нужно перевести в mn; если минимум стоял на hi (например, [5,3,1]), то после первого обмена максимум уже на hi, коррекция даёт mx = hi, и второй обмен пропускается.

Рис. 4. Двусторонняя выбором для [math]\displaystyle{ [6,2,9,5,1,3] }[/math]: за проход min и max; после min-обмена [math]\displaystyle{ [1,2,9,5,6,3] }[/math], после max-обмена [math]\displaystyle{ [1,2,3,5,6,9] }[/math].

Операция: выбором на связном списке

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

Пошаговое описание:

1. sorted ← NIL, tail ← NIL — пустой результат и его хвост.
2. Пока исходный список не пуст: пройти по нему и найти первый узел с минимальным ключом.
3. Извлечь этот узел из исходного списка (обновить указатели, [math]\displaystyle{ O(1) }[/math]).
4. Присоединить узел в конец sorted.
5. Вернуть sorted.

Инвариант. sorted — отсортированный по неубыванию префикс результата, содержащий все уже извлечённые элементы; head — остаток, из которого ничего не потеряно и не продублировано.

Алгоритм List-Selection-Sort(head)
Вход:  head — голова односвязного списка
Выход: голова списка, отсортированного по неубыванию
Инвариант: sorted — отсортированный префикс результата; head — остаток

1  sorted ← NIL ; tail ← NIL
2  while head ≠ NIL
3      mnPrev ← NIL ; mn ← head
4      p ← head
5      while p.next ≠ NIL                  # ищем первый минимум
6          if p.next.key < mn.key
7              mnPrev ← p ; mn ← p.next
8          p ← p.next
9      if mnPrev = NIL                    # минимум — голова остатка
10         head ← head.next
11     else
12         mnPrev.next ← mn.next
13     if sorted = NIL
14         sorted ← mn ; tail ← mn
15     else
16         tail.next ← mn ; tail ← mn
17     tail.next ← NIL
18 return sorted

Сложность: O(n²) сравнений (n−1 + n−2 + … + 1 = n(n−1)/2), O(1) дополнительных указателей
Корректность: инвариант сохраняется на каждой итерации; когда остаток пуст, sorted содержит все n элементов по неубыванию

Разбор. [5,2,4,6,1,3]: извлекаем 1 → sorted = [1], остаток [5,2,4,6,3]; затем 2 → [1,2], остаток [5,4,6,3]; затем 3 → [1,2,3], остаток [5,4,6]; затем 4 → [1,2,3,4], остаток [5,6]; затем 5 → [1,2,3,4,5], остаток [6]; затем 6 → [1,2,3,4,5,6].

Сложность. Поиск минимума в остатке длины [math]\displaystyle{ k }[/math] стоит [math]\displaystyle{ k-1 }[/math] сравнений, суммарно [math]\displaystyle{ (n-1) + (n-2) + \ldots + 1 = n(n-1)/2 = O(n^2) }[/math] сравнений; обменов нет, дополнительная память — [math]\displaystyle{ O(1) }[/math] указателей (sorted, tail, p, mn, mnPrev).

Крайние случаи. Пустой список (head = NIL) — возвращается NIL. Один элемент — один проход, результат совпадает с входом. Дубликаты: чтобы вариант остался устойчивым, нужно брать первый узел с минимальным ключом (строгое < при поиске) и присоединять в конец результата — тогда равные сохраняют исходный взаимный порядок. Отдельного рисунка для списочного варианта нет.

Сводная таблица сложности

Операция	Лучший	Средний	Худший	Память
Selection-Sort: сравнения	[math]\displaystyle{ n(n-1)/2 }[/math]	[math]\displaystyle{ n(n-1)/2 }[/math]	[math]\displaystyle{ n(n-1)/2 }[/math]	—
Selection-Sort: обмены	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ \approx n-H_n }[/math]	[math]\displaystyle{ n-1 }[/math]	—
Selection-Sort: записей	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ \approx 2(n-H_n) }[/math]	[math]\displaystyle{ 2(n-1) }[/math]	—
Selection-Sort: всё время	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ O(1) }[/math]
Double-selection: сравнения	[math]\displaystyle{ n(n+2)/2 }[/math] (чётное [math]\displaystyle{ n }[/math])	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	—
Double-selection: обмены	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ O(n) }[/math]	до [math]\displaystyle{ n }[/math]	—
Double-selection: всё время	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ O(1) }[/math]
На списке: сравнения	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	—
На списке: всё время	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ O(1) }[/math] указателей

Оговорка: в отличие от вставок, у сортировки выбором нет адаптивности: лучший случай не легче худшего по сравнениям. Но обменов и записей всегда [math]\displaystyle{ O(n) }[/math] — это единственная сильная сторона в модели дорогой записи. У двусторонней версии сравнений не меньше, а больше: два сравнения на элемент дают [math]\displaystyle{ n(n+2)/2 }[/math] для чётного [math]\displaystyle{ n }[/math] (при [math]\displaystyle{ n=6 }[/math] — 24 против 15), хотя проходов вдвое меньше. Амортизированных оценок здесь нет: каждая операция оплачивается сразу, без накопленного выигрыша.

Трассировка примера

a = [6, 2, 8, 5, 1, 3] (см. рис. 3).

[math]\displaystyle{ i }[/math]	Минимум в [math]\displaystyle{ a[i..5] }[/math]	Обмен	Массив
0	1 (поз. 4)	6 ↔ 1	[1, 2, 8, 5, 6, 3]
1	2 (поз. 1)	—	[1, 2, 8, 5, 6, 3]
2	3 (поз. 5)	8 ↔ 3	[1, 2, 3, 5, 6, 8]
3	5 (поз. 3)	—	[1, 2, 3, 5, 6, 8]
4	6 (поз. 4)	—	[1, 2, 3, 5, 6, 8]

Сравнений: [math]\displaystyle{ 5+4+3+2+1 = 15 = \frac{6\cdot5}{2} }[/math]. Обменов: 2 (на шагах 0 и 2; на шагах 1, 3, 4 минимум уже стоял на месте). Вставками тот же массив потребовал бы 10 сдвигов и 13 сравнений (с учётом финальных записей — 15 перемещений): контраст не в сравнениях, а в записях — 2 обмена (4 записи) против 15 перемещений. Обе трассировки сверены с реализацией из раздела «Служебное».

Корректность и оценка сложности

Корректность (инвариант)

Инвариант. Перед шагом [math]\displaystyle{ i }[/math] массив [math]\displaystyle{ a[0..i-1] }[/math] содержит [math]\displaystyle{ i }[/math] наименьших элементов исходного массива, отсортированных по возрастанию.

База. [math]\displaystyle{ i = 0 }[/math]: префикс пуст — верно.

Сохранение. На шаге [math]\displaystyle{ i }[/math] мы находим минимум в [math]\displaystyle{ a[i..n-1] }[/math] — это [math]\displaystyle{ (i+1) }[/math]-й по величине элемент исходного массива (все меньшие уже в префиксе). После обмена он оказывается в [math]\displaystyle{ a[i] }[/math], и префикс [math]\displaystyle{ a[0..i] }[/math] отсортирован и содержит [math]\displaystyle{ i+1 }[/math] наименьших. Инвариант сохранён.

Завершение. При [math]\displaystyle{ i = n-1 }[/math] весь массив отсортирован. [math]\displaystyle{ \square }[/math]

Точные оценки

На шаге [math]\displaystyle{ i }[/math] перебирается [math]\displaystyle{ n-i-1 }[/math] элементов, поэтому сравнений

[math]\displaystyle{ \sum_{i=0}^{n-2}(n-i-1) = \frac{n(n-1)}{2} }[/math]

— независимо от входа. Обменов не более одного на шаг, то есть [math]\displaystyle{ \le n-1 }[/math].

Неустойчивость

На рис. 5: [(2,a), (2,b), (1,c)]. Минимум (1,c) обменивается с (2,a), что перескакивает (2,b), и равные (2,a), (2,b) меняют порядок. Значит, сортировка выбором неустойчива.

Рис. 5. Неустойчивость: обмен [math]\displaystyle{ (1,c) }[/math] с [math]\displaystyle{ (2,a) }[/math] перескакивает [math]\displaystyle{ (2,b) }[/math] и меняет порядок равных.

Сравнение с альтернативами

Сводка — в таблице ниже (см. рис. 6).

Алгоритм	Сравнений	Записей	Устойчив	Адаптивен	Ниша
Выбором	всегда [math]\displaystyle{ n^2/2 }[/math]	[math]\displaystyle{ \le 2(n-1) }[/math]	нет	нет	дорогая запись
Вставками	[math]\displaystyle{ O(n+\text{inv}) }[/math]	[math]\displaystyle{ O(n+\text{inv}) }[/math]	да	да	малые, почти отсортированные
Пирамидальная	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	нет	слабо	гарантия, [math]\displaystyle{ O(1) }[/math] памяти
Быстрая	[math]\displaystyle{ O(n\log n) }[/math] ср.	[math]\displaystyle{ O(n\log n) }[/math]	нет	слабо	большие массивы
Слиянием (план)	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	да	нет	устойчивость

Рис. 6. Выбором против вставок, heapsort, quicksort и mergesort: мало записей, но всегда [math]\displaystyle{ \Theta(n^2) }[/math] сравнений.

Вердикт. По умолчанию выбором проигрывает вставкам (те адаптивны, устойчивы и сравнивают меньше) и [math]\displaystyle{ O(n\log n) }[/math]-алгоритмам. Выбирайте её, только если записи/обмены существенно дороже сравнений. Heapsort (Пирамидальная сортировка) устраняет квадратичное число сравнений, но сам делает [math]\displaystyle{ O(n\log n) }[/math] сравнений и [math]\displaystyle{ O(n\log n) }[/math] записей: сортировка выбором выигрывает у него только по числу записей — [math]\displaystyle{ O(n) }[/math] — и проигрывает по сравнениям.

Где применяется

Основные ниши перечислены ниже (см. рис. 7).

1. Флеш-память и EEPROM. Запись дорога и изнашивает ячейки; сортировка выбором делает [math]\displaystyle{ \le n-1 }[/math] обменов (до [math]\displaystyle{ 2(n-1) }[/math] записей). Почему: минимум записей важнее числа сравнений [4].

1. Встраиваемые системы. [math]\displaystyle{ O(1) }[/math] памяти, без рекурсии, короткий и предсказуемый код; на малых [math]\displaystyle{ n }[/math] сравнений немного [3].

1. Отбор top-[math]\displaystyle{ k }[/math] и [math]\displaystyle{ k }[/math]-й элемент. Идея «выбрать минимум» лежит в основе quickselect ([math]\displaystyle{ O(n) }[/math] средн.) и турнирного отбора [math]\displaystyle{ k }[/math] наименьших за [math]\displaystyle{ O(n\log k) }[/math] [1][3].

1. Пирамидальная сортировка. heapsort — это «выбор с кучей»: он снимает квадратичное число сравнений, но сам делает [math]\displaystyle{ O(n\log n) }[/math] сравнений и [math]\displaystyle{ O(n\log n) }[/math] записей; сортировка выбором экономит записи ([math]\displaystyle{ O(n) }[/math]), а не сравнения [1][2].

1. Обучение. Простейший пример с ясным инвариантом и наглядным контрастом «сравнения против записей» [1][3].

Рис. 7. Где применяется выбором: дорогая запись, embedded, top-k, обучение.

Историческая справка

Сортировка выбором — один из простейших алгоритмов сортировки. Её анализ (точное число сравнений [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] и поведение обменов) систематизирован Дональдом Кнутом в The Art of Computer Programming, т. 3 (§5.2.3) [2]; в учебниках она обычно идёт рядом с вставками и пузырьком как элементарная сортировка [1][3]. Двусторонний вариант с одновременным поиском минимума и максимума встречается в учебной литературе ⚠️ требует проверки (конкретные страницы не сверены).

Идея выбора развилась в турнирный отбор (tournament selection) и пирамидальную сортировку (Уильямс, 1964) — «выбор с кучей», устранивший квадратичное число сравнений; и в алгоритмы выбора [math]\displaystyle{ k }[/math]-го элемента (quickselect Хоара, 1961) [1][2]. Практическая ниша «дорогой записи» (флеш/EEPROM) закрепилась за выбором — её отмечают и учебники, и справочные обзоры [3][4].

Типичные ошибки и подводные камни

• Ожидание адаптивности. На отсортированном массиве сортировка выбором всё равно делает [math]\displaystyle{ n^2/2 }[/math] сравнений — не путайте с вставками.
• Ожидание устойчивости. Обмен через равные ключи нарушает их порядок (см. рис. 5).
• Обмен элемента с самим собой. swap(a[i], a[mn]) при mn = i — лишние записи; проверяйте mn ≠ i (особенно в модели дорогой записи).
• Ошибка в двустороннем варианте. Если максимум был на lo, после обмена с минимумом индекс максимума нужно скорректировать (строка 11).
• Применение на больших массивах. [math]\displaystyle{ O(n^2) }[/math] сравнений катастрофичны; на больших [math]\displaystyle{ n }[/math] — heapsort/quicksort.
• Путаница «выбором» и «выбор [math]\displaystyle{ k }[/math]-го». Сортировка выбором сортирует всё; выбор [math]\displaystyle{ k }[/math]-го (quickselect) — быстрее, если нужен один элемент.
• Смещение «записи = сравнения». В RAM запись дешева, и выигрыш сортировки выбором исчезает; считайте стоимость операций для конкретной системы.
• Рекурсивные «улучшения». Сортировка выбором и так проста; рекурсия только добавит накладных расходов.
• Число проходов в double-варианте. Сравнений не меньше, а больше: два сравнения на элемент дают [math]\displaystyle{ n(n+2)/2 }[/math] для чётного [math]\displaystyle{ n }[/math] (при [math]\displaystyle{ n=6 }[/math] — 24). Выигрыш — вдвое меньше проходов, а не сравнений.
• «Ровно [math]\displaystyle{ n }[/math] записей». Сортировка выбором делает до [math]\displaystyle{ 2(n-1) }[/math] записей; минимум в [math]\displaystyle{ n }[/math] записей достигает циклическая сортировка (cycle sort), а не сортировка выбором.
• Тип счётчиков. Для больших [math]\displaystyle{ n }[/math] число сравнений [math]\displaystyle{ \approx n^2/2 }[/math] переполняет int.

Задачи для практики

1. Базовая реализация. Реализуйте сортировку выбором и проверьте, что сравнений всегда [math]\displaystyle{ n(n-1)/2 }[/math]. Подсказка: полный перебор остатка на каждом шаге.

1. Обмены. Докажите, что обменов не более [math]\displaystyle{ n-1 }[/math], и постройте вход, где их ровно [math]\displaystyle{ n-1 }[/math]. Подсказка: каждый шаг — не более одного обмена; подойдёт циклический сдвиг [math]\displaystyle{ [2,3,\ldots,n,1] }[/math] (обратный массив даёт лишь [math]\displaystyle{ \lfloor n/2\rfloor }[/math] обменов).

1. Двусторонняя. Реализуйте min/max-вариант и разберите тонкий случай mx == lo. Подсказка: корректировка индекса.

1. Сравнение с вставками. Для одного массива сравните число сравнений и записей выбором и вставками. Подсказка: вставки адаптивны, выбором — нет.

1. Дорогая запись. Пусть запись стоит 100 сравнений; какой алгоритм выбрать при [math]\displaystyle{ n = 100 }[/math], 1000? Подсказка: у сортировки выбором [math]\displaystyle{ \le n-1 }[/math] обменов, то есть [math]\displaystyle{ \le 2(n-1) }[/math] записей; у вставок — около [math]\displaystyle{ n^2/4 }[/math] перемещений, и сравнения при такой цене записи второстепенны.

1. top-k. Найдите [math]\displaystyle{ k }[/math] наименьших за [math]\displaystyle{ O(n\log k) }[/math] (куча) и за [math]\displaystyle{ O(n) }[/math] в среднем (quickselect). Подсказка: связь с «выбором».

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

1. Турнирный отбор. Реализуйте выбор минимума через турнирное дерево; оцените сравнения. Подсказка: дерево победителей.

Связанные темы

• Сортировка вставками — прямой конкурент; адаптивна и устойчива.
• Сортировка пузырьком — родственный обменный алгоритм (обычно хуже).
• Сортировки (план) — обзор и нижняя граница [math]\displaystyle{ \Omega(n\log n) }[/math].
• Пирамидальная сортировка — «выбор с кучей»: [math]\displaystyle{ O(n\log n) }[/math] сравнений и [math]\displaystyle{ O(n\log n) }[/math] записей.
• Быстрая сортировка — quickselect как алгоритм выбора [math]\displaystyle{ k }[/math]-го.
• Асимптотическая сложность (план) — сравнения, записи и модели стоимости.

Источники

1. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 2 (элементарные сортировки; сортировка выбором — упражнение 2.2-2), гл. 9 (выбор за линейное время).
2. Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.3 (selection sort; число сравнений и обменов).
3. Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — §2.1 (Elementary Sorts, selection sort).
4. Wikipedia: Selection sort. URL: https://en.wikipedia.org/wiki/Selection_sort.