131
правка
Изменения
→Модификации
'''Сортировка расческой''' (англ. ''comb sort'') - модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. По мере упорядочивания массива это расстояние уменьшается и как только оно достигает 1, массив "досортировывается" обычным пузырьком. Сложность - <tex> O(nlog(n)) </tex>.
'''Сортировка перемешиванием '''(англ. ''cocktail sort''), также известная как '''Шейкерная сортировка''' - разновидность пузырьковой сортировки, сортирующая массив в 2 направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в 2 раза быстрее пузырька. Сложность - <tex> O(Nn^2) </tex>, но стремится она к <tex> O(k*n) </tex>, где k - максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве.
== См. также ==
