1632
правки
Изменения
м
== Псевдокод ==Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив <tex> Aa[0..n - 1] </tex>. '''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])
'''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
odd-even_sort'''function''' oddEvenSort(a): '''for''' (i = 0; i < '''to''' n; ++i)- 1 '''if''' (i '''mod ''' 2 ==0) '''for''' (int j = 2; j < '''to''' n; j+=- 1 '''step''' 2) '''if''' (a[j] < a[j-1]) swap(a[j-1], a[j])
'''for''' (j = 1; j < '''to''' n; j+=- 1 '''step''' 2) '''if''' (a[j] < a[j-1]) swap(a[j-1], a[j])
rollbackEdits.php mass rollback
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более <tex> n - 1 </tex> проходов, где <tex> n </tex> размер массива, чтобы отсортировать массив.
== Оптимизация ==
При использовании первой оптимизации сортировка принимает следующий вид:
При использовании же обеих оптимизаций сортировка пузырьком выглядит так:
== Сложность ==
В данной сортировке выполняются всего два различных вида операции: сравнение элементов и их обмен. Поэтому время всего алгоритма <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» , 8] </tex> и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
|}
Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще два прохода, на которых ничего не изменится, в отличии отличие от алгоритма, использующего вторую оптимизацию, который сделает один проход и прекратит свою работу, так как не сделает за этот проход ни одного обмена.
== Модификации ==
=== Сортировка чет-нечет ==='''Сортировка чет-нечет''' (англ. ''odd-even sort'') {{---}} модификация пузырьковой сортировки, основанной основанная на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность {{---}} <tex> O(n^2) </tex>.
Псевдокод указан ниже:
'''else'''
Преимущество этой сортировки {{---}} на нескольких процессорах она выполняется быстрее, так как четные и нечетные индексы сортируются параллельно.
=== Сортировка расческой ===
'''Сортировка расческой''' (англ. ''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[i + jump])
swapped = ''true''
Пояснения: Изначально расстояние между сравниваемыми элементами равно <tex dpi=150> \frac{n}{k} </tex>, где <tex> k = 1{.}3 </tex> {{---}} оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком.
=== Сортировка перемешиванием ==='''Сортировка расческойперемешиванием''' (англ. ''comb cocktail sort'') , также известная как '''Шейкерная сортировка''' {{---}} модификация разновидность пузырьковой сортировки, основанной сортирующая массив в двух направлениях на сравнении элементов на расстояниикаждой итерации. По мере упорядочивания массива это расстояние уменьшается и как только оно достигает 1В среднем, массив "досортировывается" обычным пузырькомсортировка перемешиванием работает в два раза быстрее пузырька. Сложность {{---}}<tex> O(n^2) </tex>, но стремится она к <tex> O(n(log(k \cdot n)) </tex>, где <tex> k </tex> {{---}} максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Является самой быстрой квадратичной сортировкой.Псевдокод указан ниже:
'''Сортировка перемешиванием function'''shakerSort(англ. a): begin = -1 end = n - 2 ''cocktail sort'while'), также известная как ''swapped swapped = 'Шейкерная сортировка'false'' {{---}} разновидность пузырьковой сортировки begin++ '''for''' i = begin '''to''' end '''if''' a[i] > a[i + 1] swap(a[i], сортирующая массив в 2 направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в 2 раза быстрее пузырька. Сложность {{a[i + 1]) swapped = ''true'' '''if''' !swapped '''break''' swapped = ''false'' end---}} <tex '''for''' i = end '''downto''' begin '''if''' a[i] > Oa[i + 1] swap(n^2) </tex>a[i], но стремится она к <tex> O(k*na[i + 1]) </tex>, где k {{---}} максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. 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 Сортировка перемешиванием{{--- }} Википедия]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: СортировкиСортировка]][[Категория: Квадратичные сортировки]]
