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>