Поэтому, несмотря на то что авторитетная книга «Сортировка и поиск» безапелляционно заявляет, что «пузырьковая» сортировка не имеет характеристик, явно оправдывающих ее применение», исследование Экли и его сотрудников свидетельствует, что в конце концов и для этого вида сортировки может найтись свое место в ряду алгоритмов. Его существенная «неэффективность» проявляется в том, что за один раз можно перемещать элемент только на одну позицию, и это как раз делает его довольно устойчивым по отношению к шуму и гораздо более надежным, чем такие быстрые алгоритмы, как, например, сортировка с объединением, при использовании которой каждое сравнение потенциально перемещает элемент достаточно далеко. Сортировка с объединением делает этот алгоритм хрупким. Ошибка, допущенная на раннем этапе в сортировке с объединением, подобна случайному проигрышу в первом раунде турнира, который может не только перечеркнуть все надежды любимой команды на победу в чемпионате, но еще и постоянно держать ее в нижней части турнирной таблицы[10]. При этом в соревнованиях, использующих пузырьковую сортировку (лэддер), случайный проигрыш подвинул бы игрока всего лишь на одну позицию вниз.
Но по факту это не может быть названо пузырьковой сортировкой, выступающей в роли единственного и самого лучшего алгоритма перед лицом компаратора шума. Это почетное звание – единственного и лучшего – принадлежит алгоритму, который называется «сортировка путем сравнения и подсчета». Каждый элемент сравнивается со всеми остальными, генерируя число, показывающее количество элементов, бóльших, чем исходный. Это число может напрямую использоваться в качестве ранга данного элемента. Поскольку при этом попарно сравниваются все элементы, то сортировка путем сравнения и подсчета является таким же квадратично зависимым от времени алгоритмом, как и пузырьковая сортировка. Вот почему этот тип сортировки непопулярен в программировании, но при этом остается исключительно отказоустойчивым.
Функционирование данного алгоритма должно показаться вам знакомым. Сортировка путем сравнения и подсчета работает точно так же, как и циклический алгоритм. Другими словами, схема работы данного алгоритма сильно напоминает обычный спортивный сезон: каждая команда играет с любой другой командой дивизиона и в зависимости от соотношения побед и поражений формирует показатель, на базе которого потом ранжируются все команды.
Поскольку сортировка путем сравнения и подсчета – единственный наиболее устойчивый алгоритм, то квадратичная или любая другая системы должны предложить болельщикам что-то уж совсем специфическое – и такое, чтобы никто потом не ныл, если его команда не попала в плей-офф. Использование сортировки с объединением в рамках плей-офф – рискованное мероприятие, в то время как использование сортировки путем сравнения и подсчета в рамках регулярного сезона таковым не является. Сам круговой чемпионат нельзя назвать устойчивым, но турнирные таблицы, формирующиеся на основе его показателей, весьма и весьма устойчивы. Иными словами, если даже вашу команду вышибают в самом начале плей-офф, это все равно удача. Но если ваша команда не может даже добраться до плей-офф, это уже жестокая реальность. И если ваш расстроенный приятель-болельщик еще может вам посочувствовать, то от ученого вы этого никогда не дождетесь.