Сортировка перемешиванием / Shaker (cocktail, ripple, shuffle, shuttle) sort
Также известна как шейкерная или коктейльная сортировка.
Сортировка перемешиванием - это разновидность сортировки пузырьком. Отличие в том, что данная сортировка в рамках одной итерации проходит по массиву в обоих направлениях (слева направо и справа налево), тогда как сортировка пузырьком - только в одном направлении (слева направо).
Общая идея алгоритма:
Обход массива слева направо, аналогично пузырьковой - сравнение соседних элементов, меняя их местами, если левое значение больше правого. В итоге наибольшее число будет перемещено в конец массива.
Обход массива в обратном направлении (справа налево), начиная с элемента, который находится перед последним отсортированным. На этом этапе элементы также сравниваются между собой и меняются местами, чтобы наименьшее значение всегда было слева. В итоге наименьшее число будет перемещено в начало массива.
Пример реализации на Kotlin:
fun cocktailSort(a: IntArray) {
fun swap(i: Int, j: Int) {
val temp = a[i]
a[i] = a[j]
a[j] = temp
}
do {
var swapped = false
for (i in 0 until a.size - 1)
if (a[i] > a[i + 1]) {
swap(i, i + 1)
swapped = true
}
if (!swapped) break
swapped = false
for (i in a.size - 2 downTo 0)
if (a[i] > a[i + 1]) {
swap(i, i + 1)
swapped = true
}
} while (swapped)
}
