Лучший случай для пузыря Сортировка

Question

Я хочу знать, что будет лучшим вариантом для сортировки пузырьков? Может быть случай, когда, например, не может быть замены для двух последних проходов. Я делаю свою программу на языке C. Предположим, у меня есть массив из 5 элементов, и я даю элементы как 1 2 5 4 3, тогда не было бы изменений за последние 2 прохода?

Answer 1

Лучший сценарий случая - один проход. Список уже будет отсортирован.
Без обмена = сделано.

Answer 2

Пожалуйста см Bubble sort:

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

• В худшем случае производительностьO (N²)
• Лучшая производительность случайО (п)
• Средняя производительность случайО (N²)
• Худшие сложность пространственного пространстваO (п) общее, O (1) вспомогательный
• ОптимальноеНет

Answer 3

Это трудно сказать, если вы имеете в виду

1. Что в лучшем случае алгоритмическая сложность от пузырьковой сортировки, и в этом случае C# не имеет значения, ответ O(n) для уже отсортированного ввода.
2. Когда, когда-либо, вам следует подумать об использовании сортировки пузырьков.

В последнем случае, вы этого не сделаете, потому что для маленьких случаев Shell sort и Insertion sort оба опережать его. Некоторые из наиболее эффективных процедур сортировки, которые я видел, - это гибриды Quick Sort, которые используют Shell Sort для «маленьких» разделов массива.

Answer 4

Невозможно, чтобы тип пузыря не менялся на два прохода.

Проход без переустановки означает, что список уже отсортирован.

Answer 5

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

Answer 6

Тип пузыря редко - ваш лучший случай для дела. Он исключительно медленный и неэффективный. Многие другие алгоритмы сортировки выполняются быстрее. Например, вы можете использовать что-то вроде QuickSort.

Самый быстрый алгоритм сортировки, о котором я знаю, был разработан Штеффан Нильссон и описан в следующей статье.

http://www.ddj.com/architect/184404062;jsessionid=VWL2QD1NWIEIJQE1GHOSKHWATMY32JVN?_requestid=396640

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

http://en.wikipedia.org/wiki/Bubble_sort

Answer 7

Лучший случай: В лучшем случае было бы, если список уже отсортирован. a) будут сравнения, как есть, но обмены и время выполнения в O (n2) b) Но если мы сохраняем дорожку обменов в каждом проходе и завершаем проверку программы, если нет обменов. Тогда для программы потребуется только один проход и макс. (n-1) требуется сравнение в этом одиночном проходе, и мы можем сказать, что сложность имеет порядок O (n).

Answer 8

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

BUBBLESORT(A) 
1 for i = 1 to A.length - 1 
2  for j = A.length downto i + 1 
3   if A[j] < A[j - 1] 
4    exchange A[j] with A[j - 1] 

так regardles от того, сортируется массив или не существует, никто не проходит becoz, даже если строка 4 пропускается строка 2 и 3 выполнены propotionally в п2 раз

редактировать: я думаю, что я получил это википедия правы в конце концов, но один должен изменить алгоритм by addi ng, скажем, логическая переменная is_exchange, устанавливающая ее значение false перед входом во второй цикл, и если она снова становится ложной после выхода из цикла, тогда мы закончим, и в этом случае время будет O (n). Второй цикл цикла выполняется n раз

Answer 9

Существует несколько способов написания алгоритма сортировки пузырьков, похоже, со временем алгоритм стал лучше и эффективнее. Первый алгоритм сортировки пузырьков, который я узнал, приведен ниже. Алгоритм ниже Наилучший и худший случай O (n^2).

BUBBLESORT(A) 
1 for i = 1 to A.length - 1 
2  for j = A.length downto i + 1 
3   if A[j] < A[j - 1] 
4    exchange A[j] with A[j - 1] 

Алгоритм, Википедия использует (ниже), как представляется, улучшение использования флага, чтобы сказать, если элементы были заменены или нет, что позволяет алгоритм пузырьковой сортировки лучший случай, чтобы быть O (п) вместо O (N^2)

procedure bubbleSort(A : list of sortable items) 
    n = length(A) 
    repeat 
     swapped = false 
     for i = 1 to n-1 inclusive do 
      /* if this pair is out of order */ 
      if A[i-1] > A[i] then 
       /* swap them and remember something changed */ 
       swap(A[i-1], A[i]) 
       swapped = true 
      end if 
     end for 
    until not swapped 
end procedure 

Вот видео, которое помогает объяснить немного о первом алгоритме в языке программирования C: https://youtu.be/qOpNrqqTsk4