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

Question

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

Answer 1

В лучшем случае один проход. Список уже будет отсортирован.
Нет свопа = сделано.

Answer 2

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

Answer 3

См. Сортировка пузырьков :

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

• Наихудшие показатели производительности O (n²)
• Наилучшая производительность O (n)
• Средняя производительность корпуса O (n²)
• Наихудшая сложность пространства O (n) всего, O (1) вспомогательное
• Оптимально Нет

Answer 4

Существует несколько способов написания алгоритма пузырьковой сортировки, кажется, что со временем алгоритм стал лучше и эффективнее. Первый алгоритм сортировки пузырьков, который я изучил, приведен ниже. Алгоритм, приведенный ниже «Лучший и худший случай» - это 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 (n) вместо 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

Answer 5

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

Answer 6

Невозможно поменять пузырьковую сортировку на два прохода.

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

Answer 7

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

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

В последнем случае вы этого не сделаете, потому что для небольших случаев Сортировка оболочки и Сортировка вставки оба превзойдут ее. Одними из самых эффективных процедур сортировки, которые я видел, являются гибриды Quick Sort, которые используют Shell Sort для «маленьких» секций массива.

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]

так что относительно того, отсортирован массив или нет, нет ни одного прохода becoz, даже если строка 4 пропущена, строка 2 и 3 выполнены пропозиционально до n2 раз

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

Answer 9

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

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

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

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

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