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

Ответ 1

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

Ответ 4

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

Ответ 5

Это, пожалуй, самый быстрый набор крошечных.

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

Ответ 6

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

Ответ 7

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

Привет.

Ответ 8

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

Ответ 9

Bubble sort легко реализовать, и он достаточно быстро, когда у вас небольшие наборы данных.

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

void bubbleSort(vector<int>& 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;
      }
  }
}

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

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

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

Ответ 10

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

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

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

// 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;

Ответ 11

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

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

Ответ 12

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

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

Ответ 13

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

Ответ 14

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

Ответ 15

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

Ответ 16

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