Информатика · объяснение и практика

Сортировка таблицы: почему переставлять нужно всю запись

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Электронные таблицы и форматы данных · Учебная карта

Главная мысль

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

Строка описывает один объект целиком

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

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

Проверяем не только расположение чисел

Пусть исходно записаны Ника с номером 31 и баллом 8, Борис с номером 14 и баллом 3, Ася с номером 27 и баллом 6. При возрастании баллов порядок целых записей должен стать Борис, Ася, Ника. Сам столбец баллов приобретёт вид три, шесть, восемь. Но одного этого наблюдения недостаточно: такой же столбец получится и при ошибочной перестановке одних чисел рядом с неизменившимися именами.

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

Пример

Исходные пары: Мира — 12, Олег — 5, Лена — 9. Ученик оставил имена на месте, а баллы расположил как 5, 9, 12. Получилась ли сортировка участников по баллам?

Нет: Мира получила чужой балл 5, Олег — чужой 9, Лена — чужой 12. Правильные пары в порядке возрастания: Олег — 5, Лена — 9, Мира — 12. Проверять надо сохранность пары, а не только возрастающий числовой столбец.

Уникальный номер помогает проверить сохранность

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

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

От чтения к действию

А теперь — вы

До сортировки: номер 8 — Ира — 2 балла; номер 5 — Лев — 9 баллов. После сортировки по убыванию: номер 5 — Лев — 9; номер 8 — Ира — 2. Что сохранено?

Частые вопросы

Правильно отсортированный столбец баллов гарантирует правильную таблицу?

Нет. Баллы могут оказаться приписанными другим участникам. Нужно проверить целые записи и связь полей по идентификатору.

Можно сортировать один независимый список чисел?

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться