Для чего нужна пузырьковая сортировка?

Вероятно, это самый быстрый из наборов крошечный.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Привет.

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

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

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

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

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

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

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

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

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

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

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