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

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>