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>.
'''if''' (a[j] < a[j-1])
swap(a[j-1], a[j]);
jump = n
bool swapped = true;
while (jump > 1 '''and''' swapped) {
if (jump > 1)
jump /= 1.24733;
swapped = false;
for ( i = 0; i + jump < size; ++i)
if (a[i + jump]< array[i])) {
swap(array[i], array[i + jump]);
swapped = true;
