Для чего пузырьковая сортировка хороша? [закрытый]

Как будто вы пытаетесь получить доступ к объекту, который является null. Рассмотрим ниже пример:

TypeA objA;

. В это время вы только что объявили этот объект, но не инициализировали или не инициализировали. И всякий раз, когда вы пытаетесь получить доступ к каким-либо свойствам или методам в нем, он будет генерировать NullPointerException, что имеет смысл.

См. Также этот пример:

String a = null;
System.out.println(a.toString()); // NullPointerException will be thrown
45
задан Grokify 6 June 2018 в 08:04
поделиться

16 ответов

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

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

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

43
ответ дан Matthew Scharley 26 November 2019 в 20:48
поделиться

Главным образом ничто . Используйте QuickSort или SelectionSort вместо этого...!

0
ответ дан Thomas Hansen 26 November 2019 в 20:48
поделиться

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

0
ответ дан Stephan Eggermont 26 November 2019 в 20:48
поделиться

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

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

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

// 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;
1
ответ дан buti-oxa 26 November 2019 в 20:48
поделиться

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

1
ответ дан Brian Knoblauch 26 November 2019 в 20:48
поделиться

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

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

1
ответ дан Mark Ransom 26 November 2019 в 20:48
поделиться

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

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

1
ответ дан EvilTeach 26 November 2019 в 20:48
поделиться

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

2
ответ дан Brian 26 November 2019 в 20:48
поделиться

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

Пузырьковая сортировка достаточно быстра, когда Ваш набор почти отсортирован (например, один или несколько элементов не находятся в правильных положениях), в этом случае Вы лучше для чередования пересечений от с 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;
      }
  }
}

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

Donald Knuth, в его известном "Искусство Программирования", пришел к заключению, что "пузырьковая сортировка, кажется, не имеет ничего для рекомендации его, кроме броского названия и того, что это приводит к некоторым интересным теоретическим проблемам" .

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

2
ответ дан sergtk 26 November 2019 в 20:48
поделиться

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

Поздравления.

3
ответ дан Tetha 26 November 2019 в 20:48
поделиться

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

3
ответ дан The Archetypal Paul 26 November 2019 в 20:48
поделиться

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

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

7
ответ дан Cristian Libardo 26 November 2019 в 20:48
поделиться

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

10
ответ дан workmad3 26 November 2019 в 20:48
поделиться

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

19
ответ дан Bill the Lizard 26 November 2019 в 20:48
поделиться

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

2
ответ дан Jay Conrod 26 November 2019 в 20:48
поделиться

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

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

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

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

75
ответ дан 26 November 2019 в 20:48
поделиться
Другие вопросы по тегам:

Похожие вопросы: