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

void Hashing_sort(T a[], const int n)

{

int first = 0;

int last = n;

while(last > first)

{

for(int i=first; i<last-1; i++)

if(a[i] > a[i+1])

{

swap(a[i], a[i+1]);

/*

T tmp = a[i];

a[i] = a[i+1];

a[i+1] = tmp;

*/

}

--last;

for(int i=last-1; i>first; i--)

if(a[i] < a[i-1])

{

swap(a[i], a[i-1]);

/*

T tmp = a[i];

a[i] = a[i-1];

a[i-1] = tmp;

*/

}

first++;

}

} Сортировка перемешиванием (Шейкерная сортировка) (англ. 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};