"Информатика (базовый и углублённый уровни) (в 2 частях)", Поляков К.Ю., Еремин Е.А.
Сортировка — упорядочивание элементов массива по выбранному признаку, например по возрастанию или убыванию. Она помогает быстрее находить нужные данные, сравнивать значения и анализировать наборы. Важно не только получить правильный результат, но и понимать, сколько сравнений и перемещений для этого понадобится. В параграфе разбираются три простых способа: выбором, вставками и обменами.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Сортировка — упорядочивание элементов массива по заданному ключу и направлению: по возрастанию или убыванию. Ключ — это значение, по которому сравнивают элементы, например число или фамилия. Сортировка нужна, чтобы было проще просматривать набор данных, анализировать его и искать нужное значение.
Сортировка выбором — способ упорядочивания, при котором на каждом шаге находят минимальный или максимальный элемент неотсортированной части и ставят его на нужное место. Для возрастания выбирают минимум, для убывания — максимум. Такой подход помогает последовательно закреплять элементы на их окончательных позициях.
Сортировка вставками — способ, при котором очередной элемент вставляют в подходящее место уже упорядоченной части массива. Перед вставкой элементы, которые должны стоять после него, сдвигают, освобождая ячейку. Метод удобен для понимания: достаточно поддерживать порядок в уже обработанной части.
Сортировка обменами, или пузырьковая сортировка, — способ, при котором сравнивают соседние элементы и меняют их местами, если они расположены не в нужном порядке. Повторные проходы постепенно устраняют нарушения порядка. Название «пузырьковая» связано с тем, что за проход крайнее значение перемещается к своему краю массива.
Упорядоченный массив удобнее просматривать: нужные значения легко сопоставлять друг с другом, а последующие алгоритмы поиска могут использовать известный порядок. Например, при поиске можно отбрасывать часть массива, если известно, что значения расположены по возрастанию. Направление задаёт условие задачи: расписание может требовать ранжировать числа от меньшего к большему или наоборот. Поэтому до начала работы определяют ключ и нужное направление.
В сортировке выбором массив мысленно делят на отсортированную и неотсортированную части. Сначала отсортированная часть пуста, и алгоритм просматривает оставшиеся значения, чтобы найти минимум или максимум. Найденный элемент ставят на первую позицию неотсортированной области, после чего граница частей сдвигается на одну ячейку. Такой просмотр нужен, потому что без сравнения всех кандидатов нельзя быть уверенным, что выбран действительно самый маленький или самый большой элемент.
В сортировке вставками первый элемент считают упорядоченной частью, а затем по одному берут следующие значения. Чтобы найти место для очередного элемента, сравнивают его с элементами слева и сдвигают те, которые должны располагаться позже. Само значение перед сдвигами сохраняют отдельно: иначе запись в освободившиеся ячейки может его затереть. Когда нужное место найдено, сохранённое значение вставляют туда, и обработанная часть снова остаётся упорядоченной.
Пузырьковая сортировка проходит по массиву парами соседних значений. Если соседняя пара нарушает выбранный порядок, элементы меняют местами; если порядок верный, оставляют как есть. В результате крупное значение при сортировке по возрастанию перемещается вправо, и после прохода один крайний элемент уже не нужно проверять снова. Остальные элементы могут быть не на своих местах, поэтому проходы повторяют; если за проход не было ни одного обмена, порядок уже соблюдён.
Число действий зависит от того, сколько сравнений и перемещений выполняет алгоритм. Например, выбору приходится искать минимум во всей оставшейся части даже тогда, когда массив почти упорядочен, а вставки на таком массиве часто обходятся небольшим числом сдвигов. У пузырьковой сортировки число обменов зависит от того, как расположены соседние значения, а ранняя остановка возможна, если проход прошёл без обменов. Поэтому при сравнении методов учитывают и длину массива, и его исходный порядок, и то, считают ли отдельно сравнения, обмены и сдвиги.
| Характеристика | Выбором | Вставками | Обменами |
|---|---|---|---|
| Основной шаг алгоритма | Найти минимум или максимум в неотсортированной части и поставить его на её начало. | Вставить очередное значение в подходящее место упорядоченной части. | Сравнить соседние значения и при необходимости обменять их. |
| Число проходов по массиву | n − 1 проходов поиска, если в массиве n элементов. | n − 1 вставок после первого элемента. | До n − 1 проходов; при ранней остановке может быть меньше. |
| Число сравнений в худшем случае | n(n − 1)/2. | Порядка n²; точное число зависит от исходного порядка. | Порядка n²; число зависит от реализации и момента остановки. |
| Число перемещений или обменов | Не более n − 1 обменов выбранного элемента. | Сдвиги элементов и вставка; в худшем случае их порядка n². | Обмены соседей; в худшем случае их порядка n². |
| Поведение на уже упорядоченном массиве | Сравнения всё равно выполняются при поиске очередного минимума. | Работает особенно быстро: достаточно проверить, что элементы уже стоят правильно. | При проверке обменов за проход завершает работу без перестановок. |
| Когда алгоритм удобно применять | Для небольших массивов, когда важна простая схема и мало обменов. | Для небольших массивов или почти упорядоченных данных. | Для изучения соседних обменов и небольших наборов данных. |
В таблице n обозначает количество элементов массива, а оценки «порядка n²» описывают рост числа действий при увеличении массива. Выбирайте строку в зависимости от задачи: например, если данные почти упорядочены, особенно полезно сравнить поведение вставок и обменов. Сравнение числа обменов не заменяет подсчёт сравнений: разные алгоритмы могут выполнять много проверок, но мало перестановок.
Условие: упорядочить массив из пяти различных чисел методом выбора и записать его после каждого шага. Возьмём массив 7, 3, 9, 1, 5. На каждом шаге будем искать минимум только в той части, которая ещё не отсортирована, и ставить его в её начало.
Проверяем результат: числа идут от меньшего к большему, и все исходные значения сохранены. Ответ: 1, 3, 5, 7, 9. В этом примере один шаг не изменил массив, но его проверка всё равно нужна, чтобы убедиться, что выбранный элемент уже стоит правильно.
Условие: отсортировать по убыванию массив с повторяющимися значениями методом вставок. Возьмём последовательность 4, 2, 4, 1. Первое значение считаем упорядоченной частью, а каждое следующее вставляем так, чтобы большие значения оставались левее меньших.
После каждого шага обработанная часть остаётся упорядоченной по убыванию. Равные четвёрки не мешают сортировке: их можно оставить в исходном взаимном порядке, поскольку они равны. Ответ: 4, 4, 2, 1.
Условие: определить число сравнений и обменов и выяснить, можно ли закончить раньше. Для примера возьмём 3, 1, 2 и будем сортировать по возрастанию, проходя от начала к концу и меняя соседей, если левый больше правого. Признак обмена — логическая переменная, которую перед каждым проходом устанавливают в значение «нет».
Отсутствие обменов означает, что ни одна соседняя пара не нарушает порядок, следовательно, массив отсортирован. Ответ: всего выполнено три сравнения и два обмена; алгоритм завершился после второго прохода, хотя при заранее заданном числе проходов можно было бы продолжить лишние проверки. Проверка признака обмена позволяет остановиться раньше, когда данные уже упорядочены.
Обмен без проверки условия порядка может нарушить уже правильное расположение соседей или направить сортировку не туда. Такую ошибку допускают, когда механически копируют действие алгоритма, не уточнив направление. Проверьте условие на паре, которая уже стоит верно: для возрастания левое значение не должно быть больше правого, а для убывания — меньше.
При выборе минимума или максимума иногда просматривают весь массив, включая уже отсортированную часть. Тогда алгоритм может снова выбрать значение, которое закреплено на своём месте, и не продвинуть границу. Это происходит, если забыть, где начинается неотсортированная область. Проверяйте диапазон поиска на каждом шаге и убедитесь, что новый выбранный элемент берётся именно из оставшейся части.
При вставке сдвигают элементы, но не сохраняют значение, которое нужно вставить. Тогда первая же запись может затереть его, и в массиве окажется неверный набор чисел. Ошибка возникает из-за того, что сдвиги выглядят как обычная перестановка, хотя значение временно нужно хранить отдельно. Перед сдвигами запишите его во временную переменную, а после сдвигов поместите в освободившуюся ячейку.
Один проход пузырьковой сортировки не обязательно упорядочивает весь массив. За проход крайнее значение действительно доходит до нужного края, но другие значения могут успеть переместиться только на часть пути. Чтобы проверить себя, рассмотрите после прохода все соседние пары, а не только последнюю; если где-то порядок нарушен, нужен следующий проход.
Для работы с сортировками нужно уверенно пользоваться массивами и индексами: именно индекс помогает выбрать текущую позицию и границу обработанной части. Циклы организуют повторные проходы, а условные операторы задают правило сравнения и определяют, нужен ли обмен или сдвиг. Эти знания связывают отдельные команды в алгоритм.
Сортировка пригодится при изучении поиска в упорядоченных массивах: предварительный порядок позволяет строить более эффективный поиск. Сравнение количества сравнений и перестановок развивает навык оценки эффективности алгоритмов. Те же приёмы применяют при обработке наборов данных, например при упорядочивании результатов, значений или записей по выбранному признаку.
Чем сортировка выбором отличается от сортировки вставками?
При сортировке выбором на каждом шаге ищут наименьшее значение в неотсортированной части и переставляют его в начало этой части. При сортировке вставками очередное значение помещают в подходящее место уже упорядоченной части, сдвигая мешающие элементы.
Как изменить алгоритм, чтобы сортировать по убыванию?
Нужно изменить условие сравнения так, чтобы алгоритм ставил раньше большие значения, а не меньшие. Например, при выборе ищут максимум, а при вставке или обмене перемещают меньшие значения вправо.
Почему после одного прохода пузырьковой сортировки массив может остаться неупорядоченным?
За проход сравниваются только соседние элементы, поэтому небольшие значения могут переместиться в нужную сторону лишь на одну позицию. При этом один крайний элемент гарантированно оказывается на своём месте, но для остальных могут понадобиться новые проходы.
Что делать с повторяющимися элементами при сортировке?
Их можно обрабатывать теми же правилами сравнения, что и остальные значения: равные элементы не требуется менять местами. Если важно сохранить исходный порядок равных элементов, выбирают алгоритм, который является устойчивым, или проверяют, что конкретная реализация сохраняет этот порядок.
Как определить, сколько раз алгоритм сравнивает элементы?
Нужно проследить его шаги и посчитать каждое сравнение значений массива, не смешивая их со сравнениями индексов или проверками условий цикла. Важно учитывать длину массива, выбранный алгоритм и то, зависит ли число сравнений от исходного порядка.
§ 64. Сортировка
