243
правки
Изменения
→Источники информации
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более <tex> n - 1 </tex> проходов, где <tex> n </tex> размер массива, чтобы отсортировать массив.
== Оптимизация ==
При использовании первой оптимизации сортировка принимает следующий вид:
'''function''' bubbleSort(Aa): '''for''' i = 0 '''to''' n - 2 '''for''' j = 0 '''to''' n - i - 2 '''if''' Aa[j] > Aa[j + 1] swap(Aa[j], Aa[j + 1])
При использовании же обеих оптимизаций сортировка пузырьком выглядит так:
'''function''' bubbleSort(Aa): i = 0 t = ''true'' '''while''' t t = ''false'' '''for''' j = 0 '''to''' n - i - 2 '''if''' Aa[j] > Aa[j + 1] swap(Aa[j], Aa[j + 1]) t = ''true'' i = i + 1
== Сложность ==
В данной сортировке выполняются всего два различных вида операции: сравнение элементов и их обмен. Поэтому время всего алгоритма <tex> T = T_1 + T_2 </tex>, где <tex> T_1 </tex> {{---}} время, затрачиваемое на сравнение элементов, а <tex> T_2 </tex> {{---}} время, за которое мы производим все необходимые обмены элементов.
Так как в алгоритме меняться местами могут только соседние элементы, то каждый обмен уменьшает количество [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по убыванию. Несложно посчитать, что количество инверсий в таком массиве <texdpi=150> \frac {n (n - 1)} {2} </tex>. Получаем, что <tex> T_2 = O(n^2) </tex>.
В неоптимизированной реализации на каждой итерации внутреннего цикла производятся <tex> n - 1 </tex> сравнений, а так как внутренний цикл запускается также <tex> n - 1 </tex> раз, то за весь алгоритм сортировки производятся <tex> (n - 1)^2 </tex> сравнений.
В оптимизированной версии точное количество сравнений зависит от исходного массива. Известно, что худший случай равен <texdpi=150> \frac {n (n - 1)} {2} </tex>, а лучший {{---}} <tex> n-1 </tex>. Следовательно, <tex> T_1 = O(n^2) </tex>.
В итоге получаем <tex> T = T_1 + T_2 = O(n^2) + O(n^2) = O(n^2) </tex>.
== Пример работы алгоритма ==
Возьмём массив с числами <tex> [5, 1, 4, 2, 8] </tex> и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
|}
Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще два прохода, на которых ничего не изменится, в отличии отличие от алгоритма, использующего вторую оптимизацию, который сделает один проход и прекратит свою работу, так как не сделает за этот проход ни одного обмена.
== Модификации ==
'''function''' oddEvenSort(a):
'''for''' i = 0 '''to''' n - 1
Преимущество этой сортировки {{---}} на нескольких процессорах она выполняется быстрее, так как четные и нечетные индексы сортируются параллельно.
=== Сортировка расческой ===
'''Сортировка расческой''' (англ. ''comb sort'') {{---}} модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность {{---}}<tex> O(n^2) </tex>, но стремится к <tex> O(n \log n) </tex>. Является самой быстрой квадратичной сортировкой. Недостаток {{---}} она неустойчива. Псевдокод указан ниже:
=== Сортировка перемешиванием ===
'''Сортировка перемешиванием''' (англ. ''cocktail sort''), также известная как '''Шейкерная сортировка''' {{---}} разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность {{---}} <tex> O(n^2) </tex>, но стремится она к <tex> O(k \cdot n) </tex>, где <tex> k </tex> {{---}} максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:
== См. также ==
* [[Сортировка подсчетом]]
== Ссылки Источники информации ==
* [http://en.wikipedia.org/wiki/Bubble_sort Сортировка пузырьком {{---}} Википедия]
* [http://rain.ifmo.ru/cat/view.php/vis/sorts/quadratic-2010 Визуализатор]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: СортировкиСортировка]][[Категория: Квадратичные сортировки]]
