Вы здесь

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

Исходный код на C++: 

Теория

Шейкер сортировка принимает во внимания тот факт, что от последней перестановки до конца (начала) массива находятся отсортированные элементы. Учитывая данный факт, просмотр осуществляется не до конца (начала) массива, а до конкретной позиции. Поэтому при использовании Шейкер сортировки необходимо запоминать индекс последней перестановки. На следующем шаге цикла начнём просмотр с последней перестановки. Просмотр массива осуществляется слева направо (устанавливается правая граница). Затем справа налево (устанавливается левая граница). Просмотр массива осуществляется до тех пор, пока все элементы не встанут в порядке возрастания (убывания). Приведём пример: дан входной массив чисел: 33,7,15,11,0,4,25,-1.Первый шаг работы алгоритма.
Сравниваем 33 с 7. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,33,15,11,0,4,25,-1.
Сравниваем 33 с 15. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,33,11,0,4,25,-1.
Сравниваем 33 с 11. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,33,0,4,25,-1.
Сравниваем 33 с 0. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,0,33,4,25,-1 и т.д.
Сравниваем 33 с -1. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,0,4,25,-1,33. Затем меняем направление просмотра и продолжаем процесс.
Сравниваем 25 с -1. . Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,0,4,-1,25,33.
Сравниваем 4 с -1. . Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,0,-1,4,25,33 и т.д.
Сравниваем 7 с -1. . Меняем местами элементы и сохраняем позицию перестановки. Массив равен -1,7,15,11,0,4,25,33. В итоге получаем после первого шага Шейкер сортировки (рис. 1).

После первого шага сортировки
рис. 1. Первый шаг работы алгоритма.

После первого шага алгоритма на (рис.1) видно, что -1 и 33 заняли соответствующие позиции. Таким образом, левая граница равна 1, а правая 7. Повторяем процесс. Получаем после второго шага (рис. 2).

После второго шага сортировки
рис. 2. Второй шаг работы алгоритма.

Продолжая итерационный процесс, мы получаем отсортированный массив.

Программная реализация

void sort_sheker(int count,double *mass)
{
int i,left,right,b;
double t;
for(right=count-1,left=0,b=-1;b!=0;)//устанавливаем правую и левую границу
{
b=0;
for(i=left;i<right;i++)//двигаемся слева направо
{
if(mass[i]>mass[i+1])
{t=mass[i];mass[i]=mass[i+1];mass[i+1]=t;b=i;}
}
right=b;
for(i=right;i>left;i--)//двигаемся справа налево
{
if(mass[i-1]>mass[i])
{t=mass[i];mass[i]=mass[i-1];mass[i-1]=t;b=i;}
}
left=b;
}
}