Изменения

Перейти к: навигация, поиск

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

2996 байт добавлено, 19:41, 4 сентября 2022
м
rollbackEdits.php mass rollback
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более <tex> n - 1 </tex> проходов, где <tex> n </tex> размер массива, чтобы отсортировать массив.
== Псевдокод ==Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив <tex> Aa[0..n - 1] </tex>. BubbleSort '''function''' bubbleSort(Aa): '''for''' i = 0 '''to''' n - 2: '''for''' j = 0 '''to''' n - 2: '''if''' Aa[j] > Aa[j + 1]: swap(Aa[j], Aa[j + 1]);
== Оптимизация ==
При использовании первой оптимизации сортировка принимает следующий вид:
BubbleSort '''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]);
При использовании же обеих оптимизаций сортировка пузырьком выглядит так:
BubbleSort '''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>.
== Пример работы алгоритма ==
Возьмём массив с числами «5 <tex> [5, 1 , 4 , 2 , 8] </tex> и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
|}
Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще два прохода, на которых ничего не изменится, в отличии отличие от алгоритма, использующего вторую оптимизацию, который сделает один проход и прекратит свою работу, так как не сделает за этот проход ни одного обмена.
== Модификации ==
[http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort Сортировка чет-нечет] - модификация пузырьковой сортировки, основанной на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность - <tex> O(n^2) </tex>.
[http://en=== Сортировка чет-нечет ==='''Сортировка чет-нечет''' (англ.wikipedia.org/wiki/Comb_sort Сортировка расческой] ''odd-even sort'') {{--- }} модификация пузырьковой сортировки, основанной основанная на сравнении элементов стоящих на расстоянии. По мере упорядочивания массива это расстояние уменьшается четных и как только оно достигает 1, массив "досортировывается" обычным пузырькомнечетных позициях независимо друг от друга. Сложность {{- --}} <tex> O(nlog(n)^2) </tex>.Псевдокод указан ниже: '''function''' oddEvenSort(a): '''for''' i = 0 '''to''' n - 1 '''if''' i '''mod''' 2 == 0 '''for''' j = 2 '''to''' n - 1 '''step''' 2 '''if''' a[j] < a[j - 1] swap(a[j - 1], a[j]) '''else''' '''for''' j = 1 '''to''' n - 1 '''step''' 2 '''if''' a[j] < a[j - 1] swap(a[j - 1], a[j])
Преимущество этой сортировки {{---}} на нескольких процессорах она выполняется быстрее, так как четные и нечетные индексы сортируются параллельно. === Сортировка расческой ==='''Сортировка расческой''' (англ. ''comb sort'') {{---}} модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность {{---}} <tex> O(n^2) </tex>, но стремится к <tex> O(n \log n) </tex>. Является самой быстрой квадратичной сортировкой. Недостаток {{---}} она неустойчива. Псевдокод указан ниже:  '''function''' combSort(a): k = 1.3 jump = n '''bool''' swapped = ''true'' '''while''' jump > 1 '''and''' swapped '''if''' jump > 1 jump /= k swapped = ''false'' '''for''' i = 0 '''to''' size - jump - 1 '''if''' a[i + jump] < a[i] swap(a[i], a[httpi + jump]) swapped = ''true''Пояснения:Изначально расстояние между сравниваемыми элементами равно <tex dpi=150> \frac{n}{k} </tex>, где <tex> k = 1{.}3 </entex> {{---}} оптимальное число для этого алгоритма.wikipediaСортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу.org/wiki/Cocktail_sort Когда расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком. === Сортировка перемешиванием] ==='''Сортировка перемешиванием''' (англ. ''cocktail sort''), также известная как '''Шейкерная сортировка''' {{--- }} разновидность пузырьковой сортировки, сортирующая массив в 2 двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в 2 два раза быстрее пузырька. Сложность {{- --}} <tex> O(Nn^2) </tex>, но стремится она к <tex> O(k \cdot n) </tex>, где <tex> k </tex> {{---}} максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве.Псевдокод указан ниже:  '''function''' shakerSort(a): begin = -1 end = n - 2 '''while''' swapped swapped = ''false'' begin++ '''for''' i = begin '''to''' end '''if''' a[i] > a[i + 1] swap(a[i], a[i + 1]) swapped = ''true'' '''if''' !swapped '''break''' swapped = ''false'' end-- '''for''' i = end '''downto''' begin '''if''' a[i] > a[i + 1] swap(a[i], a[i + 1]) swapped = ''true''
== См. также ==
* [[Сортировка подсчетом]]
== Ссылки Источники информации ==* [http://en.wikipedia.org/wiki/Bubble_sort Сортировка пузырьком {{---}} Википедия]
* [http://rain.ifmo.ru/cat/view.php/vis/sorts/quadratic-2010 Визуализатор]
* [http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort Сортировка чет-нечет {{---}} Википедия]
* [http://en.wikipedia.org/wiki/Comb_sort Сортировка расческой {{---}} Википедия]
* [http://en.wikipedia.org/wiki/Cocktail_sort Сортировка перемешиванием {{---}} Википедия]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: СортировкиСортировка]][[Категория: Квадратичные сортировки]]
1632
правки

Навигация