131
правка
Изменения
→Модификации
'''Сортировка перемешиванием '''(англ. ''cocktail sort''), также известная как '''Шейкерная сортировка''' {{---}} разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность {{---}} <tex> O(n^2) </tex>, но стремится она к <tex> O(k \cdot n) </tex>, где k {{---}} максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:
'''function''' Shakersort: '''while''' swapped swapped = '''false''' '''for''' (int i = 0; i < n/2; i++) beg = 0; end = n - 1; '''whileto''' beg<=end do n - 2 '''if''' aA[begi] >aA[beg i+ 1] Swap swap(aA[begi],aA[begi+1]); swapped = '''true''' '''if''' swapped = '''false''' '''break''' \\выходим из while'а beg++ swapped = '''false''' '''for''' i = n-2 '''downto''' 0 '''if''' aA[end-1i] > aA[endi+1] Swap swap (aA[end - 1i], aA[endi+1]); end--; swapped = '''true'''
== См. также ==
