Bubblesort над другими алгоритмами сортировки?

Question

Почему вы выбрали бы пузырьковую сортировку по сравнению с другими алгоритмами сортировки?

Answer 1

Вы бы не.

Оуэн Астрахан из Университета Дьюка однажды написал исследовательскую работу, в которой прослеживается история сортировки пузырьков и цитируется легенда CS Дон Кнут, в которой говорится

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

В статье указывается

В этой статье мы исследовали происхождение пузырькового сорта и его длительную популярность, несмотря на предостережения против его использования многими экспертами. Мы подтверждаем предупреждения, анализируя их сложность как в кодировании, так и во время выполнения.

Пузырьковая сортировка медленнее, чем другие O (n ² ); он примерно в четыре раза медленнее сортировки вставкой и в два раза медленнее сортировки выделения. Он имеет хорошее поведение в лучшем случае, но практически непрактичен почти для всех реальных наборов данных. Любая хорошая реализация быстрой сортировки, heapsort или mergesort может превзойти его с большим отрывом.

Также, Президент Соединенных Штатов говорит, что вы не должны его использовать.

Answer 2

Вы бы реализовали пузырьковую сортировку, если бы вам нужно было создать веб-страницу, показывающую анимацию пузырьковой сортировки в действии .

Answer 3

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

Кроме этого, это совершенно бесполезно, ИМО. Даже оправдание быстрого запуска и запуска - это нонсенс, по крайней мере, на мой взгляд. Сортировка выбора или вставка сортировки легче написать и / или понять.

Answer 4

Когда выполняются все следующие условия

• Скорость реализации намного важнее, чем скорость выполнения (вероятность <1%) </li>
• Пузырьковая сортировка - единственный алгоритм сортировки, который вы помните из университетского класса (вероятность 99%)
• У вас нет библиотеки сортировки под рукой (вероятность <1%) </li>
• У вас нет доступа к Google (вероятность <1%) </li>

Вероятность того, что вам понадобится реализовать пузырьковую сортировку, будет меньше 0,000099%, то есть менее одного на миллион.

Answer 5

Если ваши данные находятся на ленте, которая быстро читается вперед, медленно перематывается назад и быстро перематывается (или является циклом, поэтому перемотка не требуется), то пузырьковая сортировка будет работать достаточно хорошо.

Answer 6

Я могу придумать несколько причин для пузырьковой сортировки:

1. Это базовый элементарный вид. Они отлично подходят для начинающих программистов, изучающих операторы if, for и while.

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

3. Очень легко запомнить и работать с любым алгоритмом.

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

5. Теперь я чувствую себя неубедительной коммерческой рекламой о пузырчатой ​​сортировке, поэтому сейчас я буду молчать.

Answer 7

Bubble sort легко реализовать. В то время как «стандартная» реализация имеет низкую производительность, существует очень простая оптимизация, которая делает ее сильным соперником по сравнению со многими другими простыми алгоритмами. Google 'Combsort', и увидеть магию нескольких хорошо расположенных линий. Быстрая сортировка по-прежнему превосходит это, но менее очевидна для реализации и нуждается в языке, который поддерживает рекурсивные реализации.

Answer 8

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

Даже в этом случае сортировка при вставке, вероятно, будет лучше.

И если это вопрос с подвохом, в следующий разпредложить Bogosort в качестве альтернативы.В конце концов, если они ищут плохую сортировку, это путь.

Answer 9

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

Answer 10

При демонстрации на конкретном примере, как не реализовать процедуру сортировки.