131
правка
Изменения
→Модификации
[http://en.wikipedia.org/wiki/Comb_sort Сортировка расческой] - модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. По мере упорядочивания массива это расстояние уменьшается и как только оно достигает 1, массив "досортировывается" обычным пузырьком. Сложность - <tex> O(nlog(n)) </tex>.
'''Шаг 1''' мы вычисляем k которое равно
[http://en.wikipedia.org/wiki/Cocktail_sort Сортировка перемешиванием] - разновидность пузырьковой сортировки, сортирующая массив в 2 направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в 2 раза быстрее пузырька. Сложность - <tex> O(N^2) </tex>.
В оптимизированной версии точное количество сравнений зависит от исходного массива. Но точно известно, что их количество не меньше, чем количество обменов, и не больше, чем <tex> (n - 1)^2 </tex> {{---}} максимальное количество сравнений для данной сортировки. Следовательно, <tex> T_1 = 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]);
