Сортировка массива методом выбора

Сортировка выбором (selection sort) – классический детерминированный алгоритм упорядочивания массива, основанный на многократном выборе экстремального (минимального или максимального) элемента из неотсортированной части и помещении его на следующую позицию в отсортированной части. Алгоритм концептуально прост, прозрачный для доказательства корректности и анализа трудоёмкости, что делает его идеальным объектом для тренировки алгоритмического мышления при подготовке к ЕГЭ по информатике.

Формальная спецификация и инварианты

1. Спецификация задачи сортировки
   

   Вход: массив A[0..n-1], элементы из линейно упорядоченного множества.
   Выход: перестановка элементов A, удовлетворяющая условию монотонности:

   A[0] ≤ A[1] ≤ ... ≤ A[n-1].

2. Идея метода выбора
   На i-й итерации (i идёт слева направо) ищем индекс минимального элемента m на отрезке A[i..n-1], затем обмениваем A[i] и A[m]. После этого позиция i навсегда занимает окончательное значение.

3. Инвариант цикла (ключевой для доказательства корректности)
   

   Пусть внешний цикл проходит i = 0..n-2. Инвариант:

   I(i): после завершения итерации i-1 (или до начала при i=0)

   A[0..i-1] – отсортированная по неубыванию часть,

   каждый её элемент ≤ любого элемента из A[i..n-1].

   • Инициализация: при i=0 отсортированная часть пуста – инвариант истинный тривиально.

   • Сохранение: поиск минимума на A[i..n-1] и обмен с A[i] делает A[i] минимальным из остатка; упорядоченность A[0..i] сохраняется.

   • Завершение: при i = n-1 отсортирована вся последовательность.

4. Вариант (функция спуска) для завершимости
   Количество неотсортированных элементов V(i) = n - i. На каждой итерации V уменьшается на 1 ⇒ алгоритм заканчивается за конечное число шагов.

Псевдокод и корректная индексация

1. Псевдокод (неубывание, классическая реализация)
   

   SelectionSort(A[0..n-1]):

     for i := 0 to n-2 do

         m := i

         for j := i+1 to n-1 do

             if A[j] < A[m] then m := j

         if m ≠ i then swap(A[i], A[m])

   Правила индексации:

   • Внешний цикл идёт до n-2 (последний элемент автоматически окажется на месте).

   • Внутренний цикл ищет минимум на полуинтервале [i+1..n-1].

   • Обмен выполнять только при m ≠ i, чтобы избежать лишней перезаписи.

2. Вариант «по максимуму» (упорядочивание по возрастанию справа налево)
   

   for i := n-1 downto 1 do

       m := i

       for j := 0 to i-1 do

           if A[j] > A[m] then m := j

       if m ≠ i then swap(A[i], A[m])

   Семантически эквивалентно: на каждой итерации находим максимум и ставим в хвост.

Трудоёмкость и ресурсные характеристики

1. Точное число сравнений
   

   Алгоритм неадаптивен: независимо от исходного порядка выполняет одинаковое число сравнений.

   C(n) = (n-1) + (n-2) + ... + 1 = n(n-1)/2.

2. Число обменов (перестановок)
   

   Не более одного обмена на итерацию внешнего цикла:

   S(n) ≤ n-1.

   (В удачных случаях при m = i обмена нет.)

3. Память и стабильность
   

   • Дополнительная память: O(1) (in-place).

   • Нестабильный алгоритм: равные элементы могут поменять относительный порядок из-за обменов.
     Стабилизация возможна ценой увеличения числа присваиваний: вместо обмена «вырезать» минимум и «вставить» в позицию i с сдвигом элементов вправо.

Практические варианты и инженерные правила

1. Классический выбор минимума с минимизацией присваиваний
   Используйте схему с поиском индекса минимума и единым обменом после внутреннего цикла. Это даёт малое число обменов (до n-1), что выгодно на структурах с дорогими swap-операциями.

2. Стабильная модификация (stable selection sort)
   

   Чтобы сохранить относительный порядок равных ключей:

   Находим индекс m минимума на A[i..n-1]

   x := A[m]

   пока m > i:

       A[m] := A[m-1]

       m := m - 1

   A[i] := x

   • Сравнений остаётся n(n-1)/2.

   • Присваиваний становится Θ(n^2) (за счёт сдвигов).

   • Память: O(1).

   • Алгоритм становится стабильным.

3. Двусторонний выбор (min–max selection)
   

   За одну проходку внутреннего цикла находить минимум и максимум, помещая их на позиции i и n-1-i.

   • Итераций внешнего цикла ≈ n/2.

   • Сравнений – всё равно Θ(n^2), но константа меньше.

   • Важно корректно обрабатывать случай, когда min и max попадают в одну и ту же позицию или зависят от уже выполненного обмена (сначала поставьте минимум, затем при необходимости скорректируйте индекс максимума).

4. Верификация корректности (практическое правило)
   

   Поддерживайте в коде явный инвариант (комментарием или проверками):

   Перед началом итерации i:

   - префикс A[0..i-1] отсортирован,

   - min(A[i..n-1]) будет перемещён в A[i].

5. Типичные ошибки и профилактика
   

   • Off-by-one: неверные границы циклов j. Правильно: j идёт от i+1 до n-1.

   • Лишние обмены: всегда проверяйте m ≠ i.

   • Стабильность «сама по себе»: классический вариант нестабилен – не полагайтесь на исходный порядок равных элементов.

   • Негативные индексы/пустой массив: при n ≤ 1 теле циклов выполняться не должно.

   • Сравнение сложных ключей: при сортировке структур определите строгий слабый порядок (ключевой кортеж) до начала реализации.

Связь с подготовкой к ЕГЭ по информатике

• Анализ фрагментов кода: требуется уметь проследить несколько итераций, определить количество сравнений и обменов.
• Оценка сложности: важно знать точные формулы n(n-1)/2 и ≤ n-1.
• Инварианты: грамотное описание инварианта – залог верного ответа в теоретических вопросах.
• Стабильность и устойчивость решений: в задачах на сортировку пар/записей распознавайте, где нужна стабильность и как её добиться.
• Грубая верхняя оценка времени при заданных n помогает сравнить алгоритмы и выбрать адекватный.

Мини-шпаргалка (копируемые формулы и факты)

Сравнения:   C(n) = n(n-1)/2

Обмены:      S(n) ≤ n-1

Память:      O(1), in-place

Стабильность: классический вариант – нет; стабильный – «вырезать-вставить»

Инвариант:   A[0..i-1] отсортирован и ≤ любого элемента из A[i..n-1]

Асимптотика: Θ(n^2) для любого входа

Иллюстрация на конкретном примере

Пусть A = [5, 2, 4, 2, 1].

• i=0: минимум на [0..4] – 1 при m=4; обмен A[0]↔A[4] → [1,2,4,2,5].
• i=1: минимум на [1..4] – 2 при m=1 (обмена нет).
• i=2: минимум на [2..4] – 2 при m=3; обмен A[2]↔A[3] → [1,2,2,4,5].
• i=3: минимум на [3..4] – 4 при m=3 (обмена нет).
  Итог: [1,2,2,4,5]. Обменов – 2, сравнений – 10.

Пять упражнений (академический формат)

Упражнение 1. Доказательство корректности и точный счёт операций
Дан классический псевдокод сортировки выбором.
a) Запишите инвариант внешнего цикла и докажите его тремя шагами: инициализация, сохранение, завершение.
b) Выведите формулу числа сравнений C(n) и докажите её по индукции по n.
c) Докажите, что число обменов S(n) ≤ n-1, указав условие, когда обмен не выполняется.

Упражнение 2. Отладочная трассировка и анализ стабильности
Для массива A = [(2,'a'), (1,'x'), (2,'b'), (1,'y')] требуется отсортировать по первому компоненту по неубыванию.
a) Выполните пошаговую трассировку классической сортировки выбором, указывая пары (значение, метка) на каждом обмене.
b) Покажите, сохраняется ли порядок равных ключей (2,'a' перед 2,'b'; 1,'x' перед 1,'y').
c) Предложите стабильную модификацию (§4.2) и повторите трассировку для неё.

Упражнение 3. Двусторонний выбор (min–max) и корректность индексов
Реализуйте двусторонний вариант: на каждой итерации i найти минимум на A[i..n-1-i] и максимум на том же интервале, затем поместить их в A[i] и A[n-1-i].
a) Опишите, как корректировать индекс максимума, если после перестановки минимума он «съехал».
b) Оцените точное число сравнений на одной итерации и суммарно по массиву длины n.
c) Докажите, что алгоритм завершится за ⌈n/2⌉ итераций и верно отсортирует массив.

Упражнение 4. Стабильный выбор через «вырезать-вставить»
Реализуйте стабильный вариант: вырезать минимальный элемент и сдвинуть блок вправо.
a) Оцените число присваиваний на i-й итерации и суммарно по алгоритму.
b) Сравните практическую стоимость с классическим вариантом при очень дорогих обменах (например, большие записи).
c) Приведите пример задачи, где стабильность критична (сортировка студентов по баллу с сохранением изначального порядка по фамилии).

Упражнение 5. Выбор k наименьших элементов
Требуется найти k минимальных элементов массива (без полной сортировки).
a) Предложите модификацию selection sort: выполнить только первые k итераций; докажите корректность результата на префиксе длины k.
b) Оцените трудоёмкость по сравнением и обменам в зависимости от n и k.
c) Сравните с подходом «частичная куча» (без реализации): когда ваш метод предпочтителен на ЕГЭ?

Заключение

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