131
правка
Изменения
Нет описания правки
== Псевдокод ==
Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив <tex> A[0..n - 1] </tex>.
'''for''' i = 0 '''to''' n - 2
'''for''' j = 0 '''to''' n - 2
При использовании первой оптимизации сортировка принимает следующий вид:
'''for''' i = 0 '''to''' n - 2
При использовании же обеих оптимизаций сортировка пузырьком выглядит так:
i = 0
t = ''true''
'''Сортировка чет-нечет''' (англ. ''odd-even sort'') {{---}} модификация пузырьковой сортировки, основанной на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность {{---}} <tex> O(n^2) </tex>.
Псевдокод указан ниже:
'''for''' (i = 0 to n-1 ''step'' 1)
'''if''' i '''mod ''' 2 =0
'''for''' (j = 2 to n-1 ''step'' 2)
'''if''' (a[j] < a[j-1])
'''Сортировка расческой''' (англ. ''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
Пояснения: Изначально расстояние между сравниваемыми элементами равно <tex> n/k </tex>, где k =1.3 {{---}} оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком.
'''Сортировка перемешиванием '''(англ. ''cocktail sort''), также известная как '''Шейкерная сортировка''' {{---}} разновидность пузырьковой сортировки, сортирующая массив в 2 направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в 2 раза быстрее пузырька. Сложность {{---}} <tex> O(n^2) </tex>, но стремится она к <tex> O(k*\cdot n) </tex>, где k {{---}} максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:
Shakersort:
