131
правка
Изменения
Нет описания правки
== Псевдокод ==
Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив <tex> A[0..n - 1] </tex>.
'''function''' BubbleSortbubbleSort(A):
'''for''' i = 0 '''to''' n - 2
'''for''' j = 0 '''to''' n - 2
При использовании первой оптимизации сортировка принимает следующий вид:
'''function''' BubbleSortbubbleSort(A):
'''for''' i = 0 '''to''' n - 2
'''for''' j = 0 '''to''' n - i - 2
При использовании же обеих оптимизаций сортировка пузырьком выглядит так:
'''function''' BubbleSortbubbleSort(A):
i = 0
t = ''true''
'''Сортировка чет-нечет''' (англ. ''odd-even sort'') {{---}} модификация пузырьковой сортировки, основанной на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность {{---}} <tex> O(n^2) </tex>.
Псевдокод указан ниже:
'''function''' OddEvenSortoddEvenSort(a):
'''for''' i = 0 '''to''' n-1
'''if''' i '''mod''' 2 =0
'''Сортировка расческой''' (англ. ''comb sort'') {{---}} модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность {{---}}<tex> O(n^2) </tex>, но стремится к <tex> O(n \log n) </tex>. Является самой быстрой квадратичной сортировкой. Недостаток {{---}} она неустойчива. Псевдокод указан нижеЖ
'''function''' CombSortcombSort(a):
k =1.3
jump = n
'''Сортировка перемешиванием '''(англ. ''cocktail sort''), также известная как '''Шейкерная сортировка''' {{---}} разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность {{---}} <tex> O(n^2) </tex>, но стремится она к <tex> O(k \cdot n) </tex>, где k {{---}} максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:
'''function''' ShakerSortshakerSort:
'''while''' swapped
swapped = '''false'''
