Пример реализации на С++: void ShakerSort (int n, int* x)
int Left = 0, Right = n - 1, buf = 0;
do {
for (int i = Right; i >= Left; --i) {
if (x [i - 1] > x [i]) {
buf = x [i];
x [i] = x [i -1];
x [i - 1] = buf;
}
}
Left = Left + 1;
for (int i = Left; i <= Right; ++i) {
if (x [i - 1] > x [i]) {
buf = x [i];
x [i] = x [i - 1];
x [i - 1] = buf;
}
}
Right = Right - 1;
}
while (Left <= Right);
}
Сложность
Лучшее
Среднее
Худшее
Время
O(n)
O(n2)
O(n2)
Память
O(1)
Сложность у алгоритма такая же, как и у сортировки пузырьком, однако реальное время работы лучше (обычно менее чем в два раза быстрее).
Сортировка расчёской / Comb sort Сортировка расчёской - еще одна разновидность сортировки пузырьком. Данная сортировка улучшает сортировку пузырьком за счет устранения маленьких значений в конце списка (черепах).
Достигается это тем, что вместо сравнения соседних элементов, сравниваются элементы на достаточно большом расстоянии друг от друга, постепенно уменьшая это расстояние. Сначала разрыв между элементами берётся максимальный, т.е. на единицу меньше, чем размер массива. Затем на каждой итерации расстояние уменьшается путём деления расстояния на фактор уменьшения. Так продолжается до тех пор, пока разность индексов сравниваемых элементов не достигнет единицы. Тогда сравниваются уже соседние элементы как и в сортировке пузырьком, но эта итерация будет последней.
Оптимальное значение фактора уменьшения - 1,247.
