16.1. Сортировка данных

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

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

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

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

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

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

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

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

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

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

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

Сравнение направлений сортировки

Таблица показывает, как меняются правила и расположение значений при смене направления сортировки. В первой строке данных проверяйте условие для каждой пары соседних ключей, а во второй — какое значение стоит в начале списка. Последняя строка иллюстрирует оба направления на одних и тех же ключах.

Разбор задач

Задача 1

Условие: упорядочить числа 7, 2, 5, 1 по возрастанию. Ключом здесь служит само числовое значение, потому что требуется сравнить числа между собой. Нужно получить последовательность, в которой ни одно следующее число не меньше предыдущего. Разберём числа от самого маленького к самому большому.

1. Сравниваем числа и выбираем наименьшее: это 1. Ставим его первым, так как при возрастании меньшие значения должны идти раньше. Среди оставшихся чисел продолжаем тот же выбор.
2. Из чисел 7, 2 и 5 наименьшее — 2. После него ставим 5, а затем 7, потому что 5 меньше 7. Так мы расположили все элементы, не меняя состав набора.
3. Проверяем соседние пары: 1 и 2, 2 и 5, 5 и 7. В каждой паре второе число больше первого, значит условие возрастания выполнено. Это подтверждает порядок всей последовательности.

Ответ: 1, 2, 5, 7. Здесь каждый следующий ключ не меньше предыдущего, а числа 7, 2, 5 и 1 все присутствуют в результате. Поэтому последовательность отсортирована по возрастанию.

Задача 2

Условие: упорядочить числа 7, 2, 5, 1 по убыванию и объяснить отличие результата от сортировки по возрастанию. Набор и ключ остаются прежними — сравниваются числовые значения. Меняется только направление: сначала должны идти более крупные числа. Это позволяет не перепутать изменение порядка с изменением самих данных.

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

Ответ: 7, 5, 2, 1. Отличие от результата первой задачи связано только с направлением сортировки: набор чисел не изменился. Проверка соседних пар подтверждает порядок по убыванию.

Задача 3

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

1. Для начала выбираем направление сортировки по оценкам, например по возрастанию. Сравниваем оценки и располагаем записи так, чтобы меньшая оценка стояла раньше большей. Фамилии и оценки при этом перемещаются вместе, поскольку принадлежат одному ученику.
2. Затем рассматриваем группы учеников с одинаковыми оценками. Внутри каждой такой группы сравниваем фамилии и располагаем их по алфавиту. Дополнительный ключ применяется только тогда, когда основные ключи совпадают.
3. Проверяем записи по порядку: оценки должны следовать в выбранном направлении. Если у соседей оценки равны, проверяем порядок фамилий. Такая двойная проверка охватывает и основной, и дополнительный ключ.

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

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

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

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

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

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

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

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

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

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

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