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