131
правка
Изменения
→Модификации
== Модификации ==
'''Сортировка чет-нечет''' (англ. ''odd-even sort'') {{---}} модификация пузырьковой сортировки, основанной на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность {{---}} <tex> O(n^2) </tex>.
== Псевдокод ==
odd-even_sort(a):
'''for''' (i = 0; i < n; ++i)
'''if''' (i mod 2 =0)
'''for''' (int j = 2; j < n; j+=2)
'''if''' (a[j] < a[j-1])
swap(a[j-1], a[j]);
'''else'''
'''for''' (j = 1; j < n; j+=2)
'''if''' (a[j] < a[j-1])
swap(a[j-1], a[j]);
'''Сортировка расческой''' (англ. ''comb sort'') {{---}} модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. По мере упорядочивания массива это расстояние уменьшается и как только оно достигает 1, массив "досортировывается" обычным пузырьком. Сложность {{---}}<tex> O(n^2) </tex>, но стремится к <tex> O(n(log(n)) </tex>. Является самой быстрой квадратичной сортировкой.
