Для чего нужен пузырь?

Это зависит от способа распространения ваших данных – если вы можете сделать некоторые предположения.

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

http://www.sorting-algorithms.com/

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

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

Назад, когда накопители на магнитной ленте были обычными, и машины с несколькими тысячами (слова | байты) ОЗУ (любого рода) были обычным явлением, что было достаточно реалистичным, чтобы его можно было изучать. Это обстоятельство сейчас редко, поэтому изучение типа пузырьков практически не имеет смысла, но, что еще хуже, обстоятельства, когда это оптимально, все равно не учат, поэтому даже когда / если возникла правильная ситуация, почти никто этого не поймет .

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

Он не очень много используется в реальном мире. Это хороший инструмент обучения, потому что его легко понять и быстро реализовать . У этого плохой (O (n ^ 2)) наихудший случай и средняя производительность. Он имеет хорошие результаты, когда вы знаете, что данные почти отсортированы, но есть много других алгоритмов, которые обладают этим свойством, с лучшими худшими и средними характеристиками.

В последнее время я столкнулся с большим успехом в анекдоте оптимизации. Программе нужен набор спрайтов, отсортированных по глубине каждого кадра. Порядок заклинаний не сильно изменился бы между кадрами, так как оптимизация была разбита на пузырьки с одним проходом в каждом кадре. Это было сделано в обоих направлениях (сверху вниз и снизу вверх). Таким образом, спрайты всегда были почти отсортированы с очень эффективным алгоритмом O (N).

Это, вероятно, самый быстрый для крошечных наборов.

Говоря об образовании. Ссылка на последнюю сцену сортировки сортировки , это потрясающе. Должен увидеть.

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

мы недавно использовали bubblesort в доказательстве оптимальности для алгоритма. Нам пришлось преобразовать произвольное оптимальное решение, представленное последовательностью объектов, в решение, найденное нашим алгоритмом. Поскольку наш алгоритм был просто «Сортировать по этим критериям», нам пришлось доказать, что мы можем сортировать оптимальное решение, не делая его хуже. В этом случае сортировка пузырьков была очень хорошим алгоритмом, потому что у нее есть хороший инвариант, просто заменяющий два элемента, которые находятся рядом друг с другом и находятся в неправильном порядке. Думаю, с использованием более сложных алгоритмов, по-моему, были бы расплавленные мозги.

Приветствую.

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

Сортировка Bubble проста в применении, и это достаточно быстро, когда у вас небольшие наборы данных.

Сортировка Bubble достаточно быстро, когда ваш набор почти сортирован (например, один или несколько элементов не находятся в правильных положениях), в этом случае вам лучше перебрать траверсы с 0-индекса на n-index и с n-index на 0-index , Используя C ++, он может быть реализован следующим образом:

void bubbleSort(vector& v) { // sort in ascending order bool go = true; while (go) { go = false; for (int i = 0; i+1 < v.size(); ++i) if (v[i] > v[i+1]) { swap(v[i], v[j]); go = true; } for (int i = (int)v.size()-1; i > 0; --i) if (v[i-1] > v[i]) { swap(v[i-1], v[i]); go = true; } } } 

Это может быть хорошо, если обмен двух смежных предметов – это чип и замена произвольных предметов стоит дорого.

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

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

Я использовал его в некоторых случаях для небольшого N на TRS-80 Model 1. Используя цикл for, можно было реализовать полный сортировку на одной программной строке.

Помимо этого, это хорошо для обучения, а иногда и для списков, которые находятся в упорядоченном порядке.

Я когда-то использовал его для случая, когда подавляющее большинство времени он сортировал два элемента.

В следующий раз, когда я увидел этот код, кто-то заменил его на сортировку библиотеки. Надеюсь, они сначала оценили его!

Это быстро и легко кодировать и (почти невозможно сделать неправильно). У него есть место, если вы не делаете тяжелый подъем, и нет поддержки сортировки в библиотеке.

Это то, что я использую чаще всего на самом деле. (В нашем проекте мы не можем использовать внешние библиотеки.)

Это полезно, когда я точно знаю, что dataset действительно мал, поэтому мне все равно, о скорости и нужно кратчайший и простой код.

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

 // Use sort of stooge to sort the three elements by cpFirst SwapElementsIfNeeded(&elementTop, &elementBottom); SwapElementsIfNeeded(&elementTop, &elementMiddle); SwapElementsIfNeeded(&elementMiddle, &elementBottom); *pelement1 = elementTop; *pelement2 = elementMiddle; *pelement3 = elementBottom; 

Я не могу удержаться от ответа на любые замечания о сортировке пузырьков, указав более быстрый (похоже, O (nlogn), но это на самом деле не доказано) Comb Sort . Обратите внимание, что сортировка Comb немного быстрее, если вы используете предварительно вычисленную таблицу. Сорт сортировки точно такой же, как и для пузырьковой сортировки, за исключением того, что он изначально не начинается с замены соседних элементов. Это почти так же легко реализовать / понять как сортировку пузырьков.

О да, это хороший механизм выбора. Если вы найдете его в коде, написанном кем-то, вы его не нанимаете.

В основном ничего . Вместо этого используйте QuickSort или SelectionSort …!