Когда вам понадобится сортировка пузырьками? • На пуговицах

В программной инженерии очень мало универсальных правил, но есть много около-универсальные принципы. Такие вещи, как «предпочитать композицию наследованию», почти универсальны. Мне нравится находить редкие ситуации, когда эти принципы не соблюдаются, например, когда вы этого хотите. наследование над композицией. Аналогичный почти универсальный принцип: «не используйте пузырьковая сортировка«. Некоторые даже сказали бы, что это универсальное правило, поскольку Дональд Кнут написал: «Похоже, что пузырьковая сортировка не дает никаких рекомендаций, кроме запоминающегося названия и того факта, что она приводит к некоторым интересным теоретическим проблемам». ^{Но Кнут ошибался раньшедавайте посмотрим, справедливо ли это универсальное правило только около-универсальный.}

Теоретически пузырьковая сортировка работает быстрее, чем быстрая сортировка или сортировка слиянием для небольших массивов. Это делает его полезным как часть более широкой стратегии сортировки: большинство быстрых в принципе алгоритмов сортировки работают путем рекурсивной сортировки подразделов массива, т. е. если вы применяете быструю сортировку к 2 ^ 20 случайным целым числам, в какой-то момент вы сортируете 2 ^ 17 8-целых подразделов. Переключение на пузырьковую сортировку для этих подразделов было бы хорошей оптимизацией.

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

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

1. Хотя в целом алгоритм очень медленный, каждый отдельный шаг выполняется очень быстро и легко приостанавливается.
2. Каждая замена делает массив более упорядоченным, чем был раньше. Другие виды могут перемещать значения. прочь от своих финальных позиций на промежуточных этапах.

Это действительно удобно, когда вы хотите выполнить фиксированный объем работы по сортировке на кадр. Предположим, у вас на экране несколько объектов, и некоторые из них могут перекрывать другие. Вы хотите визуализировать объекты, находящиеся ближе всего к камере. первый потому что тогда вы сможете определить, какие объекты он скрывает, а затем сэкономить время на рендеринге этих объектов. При рендеринге объектов в неупорядоченном порядке нет затрат на корректность, есть только потенциальные затраты на производительность. Итак, хотя ваш массив не нуждаться быть упорядоченным, чем более упорядоченным, тем вы счастливее. Но вы также не можете тратить слишком много времени на выполнение алгоритма сортировки, потому что у вас довольно строгие ограничения в реальном времени. Пузырьковая сортировка здесь работает очень хорошо. Вы можете запускать его понемногу в каждом кадре и получать лучший порядок, чем в начале.

Это напоминает мне об одном последнем апокрифическом варианте использования, о котором я слышал. Допустим, у вас есть случайный набор частиц случайного цвета, и вы хотите анимировать их сортировку в радужный спектр. Если вы сделаете каждый кадр анимации одним проходом пузырьковой сортировки, все частицы будут плавно перемещаться в правильные позиции. Я не смог найти ни одного примера в реальной жизни, поэтому с помощью GPT4 я нарисовал дрянную визуализацию. Код здесьпоставь это здесь.

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

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

Новая статья о Кванте!

Ладно, на самом деле я не писал это, но я сыграл роль в том, что это произошло! Некоторое время назад к нам зашел друг, и мы болтали о его работе в Quanta. В то время он работал над этим огромная статья по теории метасложностипоэтому, естественно, тема проблемы сложнее, чем NP-полные подошел, и я рекомендую ему проверить достижимость сети Петри. Так он и сделал, а потом написал Простая проблема приводит к слишком большим для нашей Вселенной числам. Боже, это так волнительно!