Просмотр кода страницы Сортировка выбором

== TL;DR ==

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

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

== Определения ==

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

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

'''На месте (in-place)''' — <math>O(1)</math> дополнительной памяти: одна переменная под индекс минимума и обмен.

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

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

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

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

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

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

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

[[Файл:sl-01-idea.svg|thumb|700px|Рис. 1. Сортировка выбором: минимум остатка меняется с первым элементом, отсортированный префикс растёт.]]

[[Файл:sl-02-swaps.svg|thumb|700px|Рис. 2. Выбором делает не более <math>n-1</math> обменов, но всегда <math>n(n-1)/2</math> сравнений — компромисс «меньше записей, больше сравнений».]]

== Устройство ==

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

[[Файл:sl-03-trace.svg|thumb|700px|Рис. 3. Трассировка <math>[6,2,8,5,1,3]</math>: два обмена (6↔1 и 8↔3), 15 сравнений.]]

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

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

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

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

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

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

# Для <math>i</math> от <math>0</math> до <math>n-2</math>: <code>mn ← i</code>.
# Для <math>j</math> от <math>i+1</math> до <math>n-1</math>: если <code>a[j] &lt; a[mn]</code>, то <code>mn ← j</code>.
# Если <code>mn ≠ i</code>, обменять <code>a[i]</code> и <code>a[mn]</code>.

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

<syntaxhighlight lang="text">
Алгоритм 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 отсортирован весь массив
</syntaxhighlight>

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

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

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

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

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

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

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

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

<syntaxhighlight lang="text">
Алгоритм 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 исправляет индекс максимума после первого обмена
</syntaxhighlight>

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

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

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

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

[[Файл:sl-04-double.svg|thumb|700px|Рис. 4. Двусторонняя выбором для <math>[6,2,9,5,1,3]</math>: за проход min и max; после min-обмена <math>[1,2,9,5,6,3]</math>, после max-обмена <math>[1,2,3,5,6,9]</math>.]]

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

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

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

# <code>sorted ← NIL</code>, <code>tail ← NIL</code> — пустой результат и его хвост.
# Пока исходный список не пуст: пройти по нему и найти '''первый''' узел с минимальным ключом.
# Извлечь этот узел из исходного списка (обновить указатели, <math>O(1)</math>).
# Присоединить узел в конец <code>sorted</code>.
# Вернуть <code>sorted</code>.

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

<syntaxhighlight lang="text">
Алгоритм 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 элементов по неубыванию
</syntaxhighlight>

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

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

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

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

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

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

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

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

{| class="wikitable"
|-
! <math>i</math> !! Минимум в <math>a[i..5]</math> !! Обмен !! Массив
|-
| 0 || 1 (поз. 4) || 6 ↔ 1 || <code>[1, 2, 8, 5, 6, 3]</code>
|-
| 1 || 2 (поз. 1) || — || <code>[1, 2, 8, 5, 6, 3]</code>
|-
| 2 || 3 (поз. 5) || 8 ↔ 3 || <code>[1, 2, 3, 5, 6, 8]</code>
|-
| 3 || 5 (поз. 3) || — || <code>[1, 2, 3, 5, 6, 8]</code>
|-
| 4 || 6 (поз. 4) || — || <code>[1, 2, 3, 5, 6, 8]</code>
|}

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

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

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

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

'''База.''' <math>i = 0</math>: префикс пуст — верно.

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

'''Завершение.''' При <math>i = n-1</math> весь массив отсортирован. <math>\square</math>

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

На шаге <math>i</math> перебирается <math>n-i-1</math> элементов, поэтому сравнений

<math display="block">\sum_{i=0}^{n-2}(n-i-1) = \frac{n(n-1)}{2}</math>

— '''независимо от входа'''. Обменов не более одного на шаг, то есть <math>\le n-1</math>.

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

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

[[Файл:sl-05-unstable.svg|thumb|700px|Рис. 5. Неустойчивость: обмен <math>(1,c)</math> с <math>(2,a)</math> перескакивает <math>(2,b)</math> и меняет порядок равных.]]

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

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

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

[[Файл:sl-06-compare.svg|thumb|700px|Рис. 6. Выбором против вставок, heapsort, quicksort и mergesort: мало записей, но всегда <math>\Theta(n^2)</math> сравнений.]]

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

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

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

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

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

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

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

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

[[Файл:sl-07-applications.svg|thumb|700px|Рис. 7. Где применяется выбором: дорогая запись, embedded, top-k, обучение.]]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

== Источники ==

# 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 (выбор за линейное время).
# Knuth D. E. ''The Art of Computer Programming''. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.3 (selection sort; число сравнений и обменов).
# Sedgewick R., Wayne K. ''Algorithms''. 4th ed. — Addison-Wesley, 2011. — §2.1 (Elementary Sorts, selection sort).
# Wikipedia: Selection sort. URL: https://en.wikipedia.org/wiki/Selection_sort.

[[Category:Сортировки]]