Alterna · 37.3 — Сортировки и поиск

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

суть и практика9 классЕГЭ №17ЕГЭ №26

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

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

sorted. Создаёт новый отсортированный список и оставляет исходный без изменений.

sort. Меняет список на месте и возвращает None.

key. Вычисляет ключ сравнения; кортеж ключей задаёт приоритет критериев.

Стабильность. Равные ключи сохраняют исходный относительный порядок в Python.

Один пример в исполнении

Запусти короткую программу и переходи по строкам. Визуализатор показывает только код, текущую строку, переменные и вывод.

Двоичный поиск применим только к отсортированной последовательности. На каждом шаге он сравнивает цель со средним элементом и отбрасывает половину диапазона. При сортировке строк сравнение лексикографическое: '12' находится раньше '3', поэтому числовые строки сначала преобразуют в int. Для ЕГЭ №26 важны условие отбора и правило при равенстве, а не только сам вызов sort.

Карта алгоритмаЧитай слева направо, затем запускай код.

1Начало
2Создать values
3Построить sorted(values)
4Исходный список не менять
5Вывести оба списка

Запомнить

result = values.sort() даст None, а не список.
До двоичного поиска докажи, что данные отсортированы.
Явно задай tie-break: что делать при равных цене, балле или имени.

Синтаксис этой страницы

sorted(values, key=None, reverse=False)

Возвращает новый отсортированный список.

values.sort(key=None, reverse=False)

Меняет values на месте и возвращает None.

lambda item: ...

Короткая функция для вычисления ключа сортировки.

key=lambda x: (x[1], x[0])

Кортеж задаёт первый и второй критерий сравнения.

list.reverse()

Меняет список на месте; не возвращает новый список.

bisect_left(a, x)

Из модуля bisect: позиция вставки x в отсортированный a слева.

range / len

Используются в ручной реализации двоичного поиска.

print

Показывает порядок для проверки.