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

Особенностью пузырьковой сортировки является то, что легкий пузырек всплывает сразу, за один проход от конца последовательности к ее началу, где бы он ни находился, в то же время тяжелый пузырек тонет очень медленно, на одну позицию за один проход. Если бы изменить направление просмотра, то тяжелый элемент опустился бы вниз за один проход. Это свойство использовано в алгоритме шейкерной сортировки, в котором чередуются направления последовательных просмотров. Шейкерная сортировка хороша тогда, когда элементы последовательности почти упорядочены.

Пример.
/'ШЕЙКЕРНАЯ СОРТИРОВКА */
include
#include
#define n 8
int A[n]={27,412,71,81,59,14,273,87};
main()
{ void ShkrSort(int A[],int nn);
int j;
printf("\n Исходный массив: \n");
for (j=0; j<n; j++)
printf("%d\t",A[j]);
printf("\n");
ShkrSort(A,n);
printf("\n Отсортированный массив :\n");
for (j=0; j<n; j++)
printf("%d\t",A[j]);
printf("\n");
getch(); return 0;
}

/* ФУНКЦИЯ ШЕЙКЕРНОЙ СОРТИРОВКИ */
void ShkrSort(int A[],int nn)
{ int i,j,k,x,L,R;
L=1; R=nn-1; k=nn-1;
do
{
for (j=R; j≥L; j--)
if (A[j-1] > A[j])
   { x=A[j-1]; A[j-1]=A[j]; A[j]=x; k=j;}
L=k+1;
/* Отладочнаяечать */
printf(“ \nL=%d",L);
for (i=0; i<nn; i++)
printf("\t%d",A[i]);
for (j=L; j≤R; j++)
if (A[j-1] > А[j])
{ x=A[j-1]; A[j-1]=A[j]; A[j]=x; k=j;}
R=k-1;
/* Отладочная печать */
printf(" \nR=%d",R);
for (i=0; i<nn; i++)
printf("\t%d",A[i]);
}
while (L<R); ассив:
}
    Исходный массив:
27    412   71   81   59   14   273   87
     Отладочная печать
L=2   14  27  412  71  81  59  87  273
R=6   14  27  71  81  59  87  273  412
L=4   14  27  59  71  81  87  273  412
R=2   14  27  59  71  81  87  273  412