Изменения

== Псевдокод ==Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив <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;

Так как в алгоритме меняться местами могут только соседние элементы, то каждый обмен уменьшает количество [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по убыванию. Несложно посчитать, что количество инверсий в таком массиве <texdpi=150> \frac {n (n - 1)} {2} </tex>. Получаем, что <tex> T_2 = O(n^2) </tex>.

В оптимизированной версии точное количество сравнений зависит от исходного массива. Но точно известноИзвестно, что их количество не меньше, чем количество обменов, и не больше, чем худший случай равен <texdpi=150> \frac {n (n - 1)^} {2 } </tex> , а лучший {{---}} максимальное количество сравнений для данной сортировки<tex> n-1 </tex>. Следовательно, <tex> T_1 = O(n^2) </tex>.

Возьмём массив с числами «5 <tex> [5, 1 , 4 , 2 8» , 8] </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 Сортировка пузырьком — {{---}} Википедия]

[[Категория: СортировкиСортировка]][[Категория: Квадратичные сортировки]]