Чем хороша пузырьковая сортировка?[закрыто]
https://stackoverflow.com/questions/276113
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Есть ли у пузырьковой сортировки какое-либо применение в реальном мире?Каждый раз, когда я вижу упоминание об одном, это всегда либо:
- Алгоритм сортировки, с которым можно учиться.
- Пример алгоритма сортировки нет использовать.
Решение
Это зависит от того, как распределяются ваши данные - можете ли вы сделать некоторые предположения.
Одна из лучших ссылок, которую я нашел, чтобы понять, когда использовать пузырьковую сортировку - или какую-то другую, - это - анимированный взгляд на алгоритмы сортировки:
Другие советы
Пузырьковая сортировка (предположительно) самая быстрая сортировка, доступная в очень определенных условиях. Первоначально он стал широко известен прежде всего потому, что он был одним из первых алгоритмов (любого рода), который был тщательно проанализирован, и было найдено доказательство того, что он был оптимальным при ограниченных обстоятельствах.
Рассмотрим файл, хранящийся на ленточном накопителе, и настолько мало оперативной памяти (или таких больших ключей), что вы можете загрузить в память только две записи в любой момент времени. Перемотка ленты достаточно медленная, поэтому произвольный доступ к файлу обычно нецелесообразен - если возможно, вы хотите обрабатывать записи последовательно, не более двух за раз.
В те времена, когда ленточные накопители были обычным делом, а машины с ОЗУ (всего несколько тысяч (слов | байтов)) были обычными, это было достаточно реалистично, чтобы их стоило изучать. Это обстоятельство теперь встречается редко, поэтому изучение пузырьковой сортировки не имеет никакого смысла вообще, но, что еще хуже, обстоятельство, когда оно оптимально, все равно не учит, поэтому даже когда / если возникла правильная ситуация, почти никто не осознает это.
Будучи самым быстрым для чрезвычайно небольшого и / или почти отсортированного набора данных, в то время как это может скрыть слабость пузырьковой сортировки (по крайней мере, до некоторой степени), сортировка вставкой всегда будет лучше / оба из них.
В реальном мире он мало используется. Это хороший инструмент обучения, потому что его легко понять и быстро реализовать . У него плохой (O (n ^ 2)) наихудший случай и средняя производительность. Он показывает хорошую производительность в лучшем случае, когда вы знаете, что данные почти отсортированы, но есть множество других алгоритмов, обладающих этим свойством, с лучшей производительностью в худшем и среднем случае.
Недавно я натолкнулся на это в анекдоте по оптимизации. Программа нуждалась в наборе спрайтов, отсортированных по глубине в каждом кадре. Порядок следования спинов между кадрами не сильно изменится, поэтому для оптимизации они были отсортированы по пузырькам с одним проходом каждого кадра. Это было сделано в обоих направлениях (сверху вниз и снизу вверх). Таким образом, спрайты всегда почти сортировались с помощью очень эффективного алгоритма O (N).
Вероятно, это самый быстрый вариант для крошечных комплектов.
Кстати, об образовании. Ссылка на последнюю сцену сортировки сортировки , это удивительно. Обязательно посмотрите.
Это хорошо для небольших наборов данных - вот почему некоторые реализации qsort переключаются на него, когда размер раздела становится небольшим. Но сортировка вставок все еще быстрее, поэтому нет никаких оснований использовать ее, кроме как в качестве учебного пособия.
недавно мы использовали пузырьковую сортировку для доказательства оптимальности алгоритма.Нам пришлось преобразовать произвольное оптимальное решение, представленное последовательностью объектов, в решение, найденное нашим алгоритмом.Поскольку наш алгоритм был просто «Сортировать по этому критерию», нам нужно было доказать, что мы можем отсортировать оптимальное решение, не ухудшив его.В этом случае пузырьковая сортировка оказалась очень хорошим алгоритмом, поскольку она имеет приятный инвариант, заключающийся в простой замене двух элементов, которые находятся рядом друг с другом и находятся в неправильном порядке.Я думаю, если использовать более сложные алгоритмы, то мозги расплавятся.
Привет.
Я думаю, что это хорошее "учение" алгоритм, потому что это очень легко понять и реализовать. Это также может быть полезно для небольших наборов данных по той же причине (хотя некоторые из алгоритмов O (n lg n) тоже довольно просты в реализации).
Я не могу удержаться, отвечая на любые замечания о пузырьковой сортировке, упоминая более быстрое (кажется, O (nlogn), но это не доказано) Сортировка гребней . Обратите внимание, что Comb-сортировка немного быстрее, если вы используете предварительно вычисленную таблицу. Сортировка гребней точно такая же, как и с пузырьковой сортировкой, за исключением того, что изначально она не начинается с замены смежных элементов. Это почти так же легко реализовать / понять, как пузырьковая сортировка.
Bubble sort прост в реализации и достаточно быстр при наличии небольших наборов данных ,
Пузырьковая сортировка достаточно быстрая, когда ваш набор почти отсортирован (например, один или несколько элементов не в правильных позициях), в этом случае вам лучше чередовать ходы от 0-index до n-index и от n-index до 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;
}
}
}
Это может быть хорошо, если обмен двух смежных элементов является чипом, а обмен произвольных элементов дорог.
Поскольку этот алгоритм прост в реализации, его легко поддерживать, и в реальном жизненном цикле приложения важно сократить усилия по поддержке.
Я использовал его в некоторых случаях для небольших N на TRS-80 Model 1. Используя цикл for, можно выполнить полную сортировку в одной строке программы.
Кроме этого, это хорошо для обучения, а иногда и для списков, которые почти в отсортированном порядке.
Однажды я использовал его для случая, когда в подавляющем большинстве случаев он сортировал два элемента.
В следующий раз, когда я увидел этот код, кто-то заменил его библиотечной сортировкой. Надеюсь, они сначала протестировали это!
Это быстро и легко кодировать и (почти невозможно сделать неправильно). Это имеет место, если вы не выполняете тяжелую работу, и нет поддержки сортировки библиотеки.
Это именно тот тип, который я использую чаще всего на самом деле. (В нашем проекте мы не можем использовать какие-либо внешние библиотеки.)
Это полезно, когда я точно знаю, что набор данных действительно мал, поэтому мне нет дела до скорости и я хочу получить самый короткий и простой код.
Пузырь - не самый низкий уровень, на который ты можешь пойти. Недавно я попал в ситуацию, когда мне нужно было отсортировать ровно три элемента. Я написал что-то вроде этого:
// 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;
О да, это хороший механизм выбора. Если вы найдете это в коде, написанном кем-то, вы не нанимаете его.
В основном ничего . Вместо этого используйте QuickSort или SelectionSort ...!
