Сортировки и поиск

Содержание и основные понятия

Сортировка переводит данные в порядок, где соседние элементы сравнимы, а последовательный выбор можно выполнять слева направо после проверки его условия корректности.
суть и практика
9 класс
ЕГЭ №17
ЕГЭ №26
01
Как это устроено
Сортировка приводит данные к порядку. После неё проще выбирать объекты, сравнивать соседей и применять двоичный поиск; но нужно знать, меняется ли исходный список.
sorted.
Создаёт новый отсортированный список и оставляет исходный без изменений.
sort.
Меняет список на месте и возвращает None.
key.
Вычисляет ключ сравнения; кортеж ключей задаёт приоритет критериев.
Стабильность.
Равные ключи сохраняют исходный относительный порядок в Python.
02
Один пример в исполнении
Запусти короткую программу и переходи по строкам. Визуализатор показывает только код, текущую строку, переменные и вывод.
Двоичный поиск применим только к отсортированной последовательности. На каждом шаге он сравнивает цель со средним элементом и отбрасывает половину диапазона. При сортировке строк сравнение лексикографическое: '12' находится раньше '3', поэтому числовые строки сначала преобразуют в int. Для ЕГЭ №26 важны условие отбора и правило при равенстве, а не только сам вызов sort.
Карта алгоритма
Читай слева направо, затем запускай код.
1
Начало
2
Создать values
3
Построить sorted(values)
4
Исходный список не менять
5
Вывести оба списка
03
Запомнить
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
Показывает порядок для проверки.