Сортировка: упорядочение и классификация

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

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

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

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

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

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

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

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

Один и тот же набор можно упорядочить по-разному, потому что у объектов часто есть несколько признаков. Книги можно расставить по фамилиям авторов, названиям или году издания, и результаты будут отличаться. Кроме того, порядок по одному ключу бывает возрастающим и убывающим. Поэтому в задании важно уточнить и ключ, и направление сортировки.

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

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

Упорядочение и классификация объектов

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

Разбор задач

Числа по возрастанию

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

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

Ответ: 1, 3, 8, 10. Такой порядок подходит, потому что каждое число больше предыдущего. Мы не меняли ключ сортировки и направление по ходу решения. Это позволяет проверить результат одним просмотром ряда.

Книги по фамилиям авторов

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

1. Для каждой книги найдём фамилию автора. Это нужно, чтобы сравнивать книги по одному выбранному ключу, а не по разным данным.
2. Сравним первые буквы фамилий по алфавиту. Если первые буквы одинаковые, перейдём к следующим буквам, пока не станет ясно, какая фамилия идёт раньше.
3. Запишем книги в найденном порядке фамилий и проверим соседние записи. У каждой пары следующая фамилия должна идти в алфавите не раньше предыдущей.

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

Животные по группам и по алфавиту

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

1. Рассмотрим каждое животное и отнесём его к домашним или диким. Принимаем решение по одному основанию — образу жизни животного, а не по первой букве названия.
2. Проверим, что для каждой карточки выбрана группа и что группы имеют понятные названия. Если неясно, куда отнести животное, нужно уточнить признак классификации.
3. Внутри каждой группы сравним названия по алфавиту и расположим карточки в таком порядке. Группы при этом не смешиваем: сортировка выполняется отдельно в каждой.

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

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

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

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

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

Если группы основаны на разных или неясных признаках, классификация становится непонятной. Например, нельзя одну группу образовать по цвету, а другую — по размеру, не объяснив общего правила. Ошибку допускают, когда делят объекты «на глаз». Для проверки сформулируйте одно основание классификации и убедитесь, что по нему можно распределить весь набор.

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

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

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

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

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

• Сортировка помогает упорядочить набор объектов.
• Для сортировки выбирают ключ — признак, по которому сравнивают объекты.
• Порядок может быть возрастающим или убывающим.
• Один набор можно упорядочить по разным ключам.
• Классификация распределяет объекты по группам.
• Основание классификации должно быть общим и понятным.