§ 21. Сортировка массива

Определения и обозначения

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

Сортировка по возрастанию — расположение элементов так, чтобы каждый следующий был не меньше предыдущего. Например, после сортировки чисел 7, 2, 5 получится 2, 5, 7. Это направление выбирают, когда нужно начать с минимального значения и двигаться к максимальному.

Сортировка по убыванию — расположение элементов так, чтобы каждый следующий был не больше предыдущего. Для тех же чисел результатом будет 7, 5, 2. Такой порядок удобен, если сначала нужно увидеть самые большие значения, например результаты с наибольшим баллом.

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

Как это устроено

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

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

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

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

Направление сортировки задаётся условием, по которому программа обнаруживает неправильный порядок. Для возрастания соседей меняют, когда левый больше правого: a[i] > a[i + 1]. Для убывания — когда левый меньше правого: a[i] < a[i + 1]. Остальную структуру алгоритма можно сохранить, если циклы по-прежнему сравнивают допустимые пары.

Сортировка массива по возрастанию и по убыванию

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

Разбор задач

Задача 1. Сортировка четырёх чисел

Упорядочим по возрастанию массив 4, 1, 3, 2 и запишем изменения после каждого обмена. Сравниваем соседей слева направо; если левое число больше правого, исправляем пару. Так виден не только итог, но и то, как значения перемещаются при проходе.

1. Сравниваем 4 и 1: порядок нарушен, поэтому меняем их местами; получаем 1, 4, 3, 2. Затем сравниваем 4 и 3, выполняем обмен и получаем 1, 3, 4, 2. Наконец, 4 больше 2, поэтому после обмена массив становится 1, 3, 2, 4.
2. В новом проходе сравниваем 1 и 3 — обмен не нужен. Пара 3 и 2 нарушает порядок, поэтому меняем её местами и получаем 1, 2, 3, 4. Число 4 уже стоит в конце, но для уверенности алгоритм может выполнить проверочный проход без обменов.

Ответ: после сортировки получаем 1, 2, 3, 4. Каждый обмен устранял нарушение в одной соседней паре, а повторный проход исправил оставшуюся пару 3 и 2.

Задача 2. Алгоритм для массива из N целых чисел

Нужно упорядочить по возрастанию массив произвольной длины N, в том числе с повторяющимися числами. Сначала удобно задать один проход по соседним парам, а затем повторить его несколько раз. Для примера возьмём 3, 1, 3, 2: повторяющиеся тройки не требуют обмена друг с другом.

1. Задаём внешний цикл для повторных проходов, например от 1 до N − 1. На каждом проходе внутренний цикл перебирает индексы i от 0 до N − 2, если нумерация массива начинается с нуля. Эти границы нужны, потому что для сравнения используется элемент с индексом i + 1.
2. Для каждой пары проверяем условие a[i] > a[i + 1]. Если оно истинно, сохраняем a[i] во временной переменной t, присваиваем a[i] значение a[i + 1], а затем записываем t в a[i + 1]. Если условие ложно, оставляем пару без изменений.
3. На примере сначала обмениваем 3 и 1, получая 1, 3, 3, 2; сравнение двух троек не приводит к обмену. Затем меняем местами 3 и 2, получая 1, 3, 2, 3, а следующий проход ставит 2 перед 3.

Ответ: результат — 1, 2, 3, 3. При проверке границ убедись, что внутренний цикл не обращается к элементу за пределами массива; равные значения допустимы и не мешают сортировке.

Задача 3. Сортировка по убыванию

Изменим алгоритм, который упорядочивал числа по возрастанию, чтобы получить обратный порядок. Проверим его на массиве 2, 5, 1, 4. Структуру циклов и способ обмена оставим прежними, поскольку изменилось только требование к расположению соседей.

1. В условии обнаружения нарушения заменяем знак > на знак <. Теперь обмен выполняется, если левый элемент меньше правого: так большее значение перемещается левее меньшего.
2. При проходе сравниваем 2 и 5 и меняем их местами, получая 5, 2, 1, 4. Пара 2 и 1 уже расположена правильно, а сравнение 1 и 4 приводит к обмену и даёт 5, 2, 4, 1.
3. В следующем проходе сравнение 2 и 4 исправляет пару: получаем 5, 4, 2, 1. Проверяем соседей: каждое следующее число не больше предыдущего, значит выбранное условие работает для убывания.

Ответ: массив после сортировки — 5, 4, 2, 1. Если программа выдаёт противоположное направление, проверь знак в условии сравнения, а не меняй значения исходных данных вручную.

Типичные ошибки

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

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

• Ошибочные границы циклов. Слишком короткий цикл может пропустить пару, а слишком длинный — обратиться к индексу за пределами массива. Часто забывают, что при сравнении используется и a[i + 1]. Проверь, что последний индекс сравниваемого элемента не превышает N − 2 при нумерации с нуля.

• Остановка после одного прохода. Один проход может переместить крайнее значение на нужное место, но остальные элементы ещё не обязательно упорядочены. Ошибка возникает, когда принимают частичный результат за готовый. Проверь массив целиком после прохода и повторяй сравнения, пока порядок не установлен.

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

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

Упорядоченные данные удобны при поиске и сравнении элементов. Сортировка также используется в задачах, где нужно расположить результаты от меньшего к большему или выделить самые большие значения. Она не заменяет поиск, но может подготовить данные так, чтобы дальнейший алгоритм решал задачу проще.

Что запомнить

• Сортировка меняет порядок элементов, а не их значения.
• До начала сортировки нужно определить требуемое направление порядка.
• Нарушение порядка выявляют сравнением элементов.
• Обмен выполняют через временную переменную, чтобы не потерять значение.
• Повторные проходы постепенно упорядочивают весь массив.
• Для обратного порядка меняют условие сравнения.