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

Книги на полке стоят как попало, и нужна одна: «Мёртвые души». Вы ведёте пальцем по корешкам слева направо, сверяете каждый с названием в голове и заканчиваете там, где нашли или где полка кончилась. Это поиск перебором, и к нему вернёмся, потому что он сильнее своей репутации.

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

Полка без порядка

Перебор в Python пишется одним выражением: x in knigi отвечает, есть ли книга в списке, а knigi.index(x) говорит, на каком она месте. Оба внутри делают ровно то, что делал палец по корешкам: проверяют подряд. Если книга стоит первой, хватит одного сравнения. Если последней или её нет вовсе, понадобится столько сравнений, сколько на полке книг. В среднем, когда искомая книга может оказаться где угодно, уходит около половины полки.

У перебора есть сильные стороны, о которых забывают, когда хвалят деление пополам. Он работает на любых данных: порядок ему не требуется, и иногда завести его просто нельзя, например когда книгу ищут по слову из аннотации, а полка расставлена по авторам. Он почти не оставляет места для ошибки, и в неупорядоченном списке проще всего отвечает на вопрос «сколько здесь книг одного автора»: knigi.count(x) просматривает весь список.

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

Деление пополам

Поиск в упорядоченном списке устроен иначе. Вы смотрите на середину. Если там нужная книга, вы закончили. Если нет, сравнение подсказывает, в какой половине она может стоять: слово «Гоголь» по алфавиту раньше, чем «Лермонтов», значит, правая половина отпала целиком. Теперь у вас полка вдвое короче, и действие повторяется.

Каждое сравнение убирает половину того, что осталось. Для тысячи книг хватает десяти сравнений (две в десятой степени — 1024, что больше тысячи). Для миллиона хватает двадцати. Для толкового словаря на сто тысяч слов (число для примера) нужно семнадцать: вы открываете словарь семнадцать раз и каждый раз понимаете, в какую половину идти. Именно так люди и ищут слово в бумажном словаре, хотя никто не называет это алгоритмом.

Пример на полке из пятнадцати авторов, расставленных по алфавиту: Ахматова, Бунин, Гоголь, Грибоедов, Достоевский, Есенин, Крылов, Лермонтов, Маяковский, Некрасов, Пушкин, Тургенев, Тютчев, Фет, Чехов. Ищем Пушкина.

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

Четыре сравнения на пятнадцать книг, и это максимум: две в четвёртой степени равно шестнадцати, а шестнадцать больше пятнадцати.

В Python готовый поиск такого вида лежит в модуле bisect:

• from bisect import bisect_left
• i = bisect_left(knigi, x)
• print(i < len(knigi) and knigi[i] == x)

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

Что стоит порядок

Из сказанного легко вывести, что отсортировать всё и искать делением пополам всегда выгоднее. Это верно не всегда, и проверяется арифметикой на пальцах.

Сортировка тоже что-то стоит. Хорошие способы расставить n книг делают порядка n·log2(n) сравнений: для тысячи это около десяти тысяч. Один перебор по той же тысяче обойдётся самое большее в тысячу. Если вам нужно найти одну книгу один раз, расставлять полку нет смысла, и проще пройти пальцем. Если искать придётся тысячу раз, расклад меняется: перебор потребует в среднем около полумиллиона сравнений (тысяча поисков по пятьсот), а сортировка плюс тысяча поисков делением пополам уложатся в двадцать тысяч, то есть примерно в двадцать пять раз быстрее.

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

Как отсортировать, и сколько писать самому

В Python сортировка — готовая функция, и организовывать её самим не надо:

• knigi_po_poryadku = sorted(knigi)
• knigi.sort()
• sorted(knigi, key=len)

Первая строка возвращает новый упорядоченный список, вторая переставляет книги в самом списке, третья упорядочивает по другому признаку: здесь по длине названия. Для задач, где данные устроены сложнее строки, именно параметр key выручает чаще всего.

Есть у сортировки ловушка, на которую попадаются все: порядок зависит от типа. Список строк ['10', '9', '2'] отсортируется в порядок '10', '2', '9', потому что строки сравниваются по символам слева направо, а единица меньше двойки. С названиями книг похоже: заглавные буквы стоят в таблице символов раньше строчных, и «Война и мир» окажется перед «анной карениной», набранной с маленькой буквы, хотя по алфавиту «а» идёт первой. Лечится ключом, sorted(knigi, key=str.lower) сравнивает названия в нижнем регистре, а числа превращают в числа до сортировки (о типах данных — в статье про переменные и типы, а о строках — в статье про строки).

Моя позиция, с которой школьный курс не согласится: сортировки пузырьком, выбором, вставками и прочие учебные нужно один раз написать руками и забыть. Каждая из них делает порядка n² сравнений: для тысячи — миллион, для миллиона — двенадцать нулей, то есть работа, которую не закончишь за разумное время. Эти алгоритмы учат, потому что на них видно, как работает перестановка и почему порядок после прохода растёт, но писать их в рабочей программе незачем: готовая сортировка быстрее на порядки. Пузырёк при этом легко написать с ошибкой, и отладка занимает больше времени, чем вывод про n², ради которого его пишут.

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

Где ломается поиск делением пополам

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

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

Когда разница становится заметна, и как это показать

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

Измерить это можно за три строки:

• from time import perf_counter
• t = perf_counter()
• print(perf_counter() - t)

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

На экзамене по информатике прямых вопросов про сортировку и поиск ждать не стоит: они прячутся внутри заданий с файлами. Там обычно два варианта данных, маленький и большой, и решение, которое проходит на первом, на втором может не уложиться во время. Как это выглядит в последней задаче, объясняет статья про задание 27 ЕГЭ по информатике; общая карта первой части лежит в статье о ней, а структура всей работы — в обзоре экзамена.

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

Начать поиск:

• каталог репетиторов по информатике
• репетиторы по информатике для подготовки к ЕГЭ
• репетиторы по информатике для 10–11 класса
• репетиторы по информатике со стажем от семи лет
• репетиторы по информатике с пробным занятием

Вопросы и ответы

Нужно ли учить сортировку пузырьком? Один раз написать стоит, чтобы увидеть, как работает перестановка. Дальше пользуйтесь готовой сортировкой: на экзамене пузырёк не нужен.

Почему поиск делением пополам требует упорядоченного списка? Каждый шаг решает, какую половину выбросить, опираясь на то, что слева меньшие элементы, справа большие. Если порядка нет, вывод «слева его быть не может» ничем не подтверждён, и поиск пропустит нужный элемент, не сообщив об этом.

Что быстрее: in для списка или поиск делением пополам? Для упорядоченного списка в тысячи элементов и больше быстрее деление пополам. Для коротких списков и однократного поиска быстрее и проще in.

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