Изменения

Перейти к: навигация, поиск

Сортировка пузырьком

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

Навигация