Сортировка перемешиванием

Сортировка перемешиванием (Шейкерная сортировка) (англ. Cocktail sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства.
Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.
Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.

Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (т.е. части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.

Лучший случай для этой сортировки — отсортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).

Наименьшее число сравнений в алгоритме Шейкер-сортировки C=N-1. Это соответствует единственному проходу по упорядоченному массиву (лучший случай)

Код программы на языке программирования С++

#include <vcl.h>
#include <conio.h>
#include <iostream.h>
#pragma hdrstop
#pragma argsused
 
// Шейкер-сортировка
 
int main(int argc, TCHAR* argv[])
{
    const int Count = 10;
    int TestArr[Count] = {3,1,5,8,1,0,6,4,6,7};
 
    ShakerSort(TestArr,1,Count);
    ArrayOutput(TestArr,0,Count);
 
    return 0;
}
 
//Поменять местами i-й и i-1-й элементы массива Arr
void Swap(int Arr[], int i)
{
    int temp;       //буфер
    temp = Arr[i];
    Arr[i] = Arr[i-1];
    Arr[i-1] = temp;
}
 
void ShakerSort(int Arr[], int Start, int N)
{
    int Left,Right; //границы сортировки
    int Last;       //место последней перестановки
 
    Left=Start;
    Right = N-1;
    Last = N-1;
 
    do
    {
        //Сдвигаем к концу массива "легкие элементы"
        for (int i =Right; i >= Left; i--)
        {
            if (Arr[i-1]>Arr[i])
            {
                Swap(Arr, i);
                Last = i; //Запомнить место последней перестановки
            }
        }
 
        Left = Last + 1;
 
        //Сдвигаем к началу массива "тяжелые элементы"
        for (int i =Left; i <= Right; i++)
        {
            if (Arr[i-1]>Arr[i])
            {
                Swap(Arr, i);
                Last = i; //Запомнить место последней перестановки
            }
        }
 
        Right = Last - 1;
    }
    while (Left<=Right);
}
 
//Вывод элементов массива на консоль
void ArrayOutput(int* Arr, int Start, int N)
{
    for (int i = 0; i < N; i++)
    {
        cout << Arr[i] << '\n';
    }
    getch();
}

Трассировка программы

3 1 5 8 1 0 4 6 6 7
3 1 5 8 0 1 4 6 6 7
3 1 5 0 8 1 4 6 6 7
3 1 0 5 8 1 4 6 6 7
3 0 1 5 8 1 4 6 6 7
0 3 1 5 8 1 4 6 6 7 Left=1
0 1 3 5 8 1 4 6 6 7
0 1 3 5 1 8 4 6 6 7
0 1 3 5 1 4 8 6 6 7
0 1 3 5 1 4 6 8 6 7
0 1 3 5 1 4 6 6 8 7
0 1 3 5 1 4 6 6 7 8 Right=8
0 1 3 1 5 4 6 6 7 8
0 1 1 3 5 4 6 6 7 8 Left=3
0 1 1 3 4 5 6 6 7 8

Ссылки

Имеется викиучебник по теме
«Примеры реализации сортировки перемешиванием»