§ 3. Упорядочение массивов

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

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

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

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

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

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

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

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

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

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

Алгоритм полезно проверить на небольшом массиве, записывая после каждого шага индексы и значения. Такая проверка помогает заметить неправильное условие, потерянный элемент или ошибку в границах цикла до запуска программы на больших данных. В конце нужно убедиться и в правильном порядке, и в том, что каждый исходный элемент остался в массиве.

Сравнение способов сортировки массива

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

Разбор задач

Задача 1. Упорядочить массив [4, 1, 3] по возрастанию способом выбора. Нужно каждый раз искать минимум только среди значений, которые ещё не заняли окончательное место. Поэтому после первого шага элемент с минимальным значением больше не участвует в поиске.

1. В начале неотсортирован весь массив. Минимум среди 4, 1, 3 — число 1, его меняем местами с первым элементом 4.
2. Получаем [1, 4, 3]. Теперь ищем минимум только в остатке [4, 3]: это 3, поэтому меняем его с первым элементом остатка.
3. Получаем [1, 3, 4]. Последний элемент уже оказывается на нужном месте, потому что в оставшейся части был только он.

Ответ: [1, 3, 4]. Каждый выбранный минимум поставлен на очередную позицию слева, поэтому массив идёт по возрастанию.

Задача 2. Упорядочить [5, 2, 4, 1] по убыванию способом обменов. Для убывания левый элемент соседней пары должен быть не меньше правого. Если слева стоит меньшее значение, пару нужно поменять местами, чтобы большие числа постепенно перемещались к началу.

1. Сравниваем 5 и 2: порядок верный, обмен не нужен; затем 2 и 4: 2 меньше 4, меняем их и получаем [5, 4, 2, 1].
2. Сравниваем 2 и 1: порядок верный, первый проход закончен. Проверяем оставшиеся соседние пары в следующем проходе; они уже расположены по убыванию.
3. Останавливаемся, когда проход не требует обменов или выполнены все необходимые проходы. Проверка пар подтверждает, что слева направо значения не увеличиваются.

Ответ: [5, 4, 2, 1]. При одинаковых соседях обмен не требуется, так как равенство не нарушает порядок по убыванию.

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

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

Ответ: алгоритм с внешним и внутренним циклами сортирует массив по возрастанию, если границы циклов не выходят за длину массива. На проверочном примере повторяющиеся значения сохранены.

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

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

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

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

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

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

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