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

Сортировка перемешиванием (Шейкерная сортировка) (англ. Cocktail sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства.

• Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.
• Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.

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

Пример:

int* ShakerSort(int* Array, int SizeArray)
{
    int i=0;
    int tmp=0;
    int left=0;
    int right=SizeArray-1;

    while(left<right)
    {
        for(i=left; i<right; i++)
        {
            if(Array[i]<Array[i+1])
            {
                tmp=Array[i];
                Array[i]=Array[i+1];
                Array[i+1]=tmp;
                tmp=i;
            }
        }
        right=tmp;
        if(left<=right)
        {
            break;
        }
        else
        {
            for(i=right; i<left; i--)
            {
                if(Array[i-1]<Array[i])
                {
                    tmp=Array[i];
                    Array[i]=Array[i-1];
                    Array[i-1]=tmp;
                    tmp=i;
                }
            }
            left=tmp;
        }
    }
    return Array;
}

---

Wiki: Шейкерная сортировка