131
правка
Изменения
→Модификации
'''Сортировка расческой''' (англ. ''comb sort'') {{---}} модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. По мере упорядочивания массива это расстояние уменьшается и как только оно достигает 1, массив "досортировывается" обычным пузырьком. Сложность {{---}}<tex> O(n^2) </tex>, но стремится к <tex> O(n(log(n)) </tex>. Является самой быстрой квадратичной сортировкой. Недостаток {{---}} она неустойчива. Псевдокод указан ниже combsort(a): 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;
'''Сортировка перемешиванием '''(англ. ''cocktail sort''), также известная как '''Шейкерная сортировка''' {{---}} разновидность пузырьковой сортировки, сортирующая массив в 2 направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в 2 раза быстрее пузырька. Сложность {{---}} <tex> O(n^2) </tex>, но стремится она к <tex> O(k*n) </tex>, где k {{---}} максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве.
