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

Суть алгоритма в том, что данные сортируются "волнообразно", при этом программа сначала проходит массив слева направо, а потом справа налево. Когда идем слева, то собираем справа большие числа, а когда справа, то собираем слева меньшие.
#include <iostream>
using namespace std;

int array[100];

void Sort(int col)
{
int trash=0;
bool f=true;
for (int i=1; (i<=col) && (f=true) ; i++)
{
f=
false;
// проходим с лева на право
for (int j=i; j<=col-i; j++)
{
// если число слева больше числа
if (array [j]>array [j+1])
{
// справа, то меняем местами
trash=array[j];
// справа собираются большие числа
array [j]=array [j+1];
array [j+1]=trash;
f=
true;
}
}

// проходим с права на лево
for (int j=col-i-1; j>i ; j--)
{
// если число справа меньше числа
if (array [j]<array[j-1])
{
// слева, то меняем местами
trash=array[j];
// слева собираются меньшие числа
array [j]=array [j-1];
array [j-1]=trash;
f=
true;
}
}
}
}

// вывод
void Out(int col)
{
for (int i=1; i<=col; i++)
cout << array [i] <<" ";
cout << endl;
}

// главная
int main()
{
int col_el;

// ввод данных
cout << " Enter length of array"<< endl;
cin >> col_el;
cout << " Enter array elements"<<endl;
for (int n=1; n<=col_el ; n++)
{
cout <<n<<" :" << "\t";
cin >> array[n];
}

// сортировка
Sort(col_el);

// вывод результата
cout << "Result is :"<<endl;
Out(col_el);
cin >> col_el;

return 0;
}
По сравнению с сортировкой методом "пузырька", эта сортировка быстрее. И выполняется за n*(n-1+n-2)*(n-2+n-3)*...*(2+1)=n*(2n-3)*(2n-5)*...*
 
« Предыдущая статья   Следующая статья »