Void ShakerSort(int *b, int Start, int n)
{ int Lt, Rt, i, t;
Lt = Start; Rt = N - 1;
while (Lt <= Rt)
{ for (i = Rt; i >= Lt; i--)
if (B[i - 1] > B[i])
{ t = B[i]; B[i] = B[i - 1]; B[i - 1] = t; }
Lt++;
for (i = Lt; i <= Rt; i++)
if (B[i - 1] > B[i])
{ t = B[i]; B[i] = B[i - 1]; B[i - 1] = t; }
Rt--;
}
}
Void main()
{ setlocale(LC_ALL, "Rus");
int i, N; int A[100];
cout<<"Количество= "; cin>>N;
for (i = 0; i < N; i++)
{ cout<<" А= "; cin>>A[i]; }
ShakerSort(A, 1, N);
cout<<"Результат: ";
for (i = 0; i < N; i++)
cout<<A[i]<<" ";
}
void ShakerSrt(int B[], int n) //другая функция шейкерной сортировки { int bf, fs = 0, m = 1, ls = n; for(; fs < ls; m > 0 ? ++fs: ls) { for (int i = m > 0 ? fs: ls;
m > 0 ? (i < ls): (i > fs); m > 0 ? ++i: --i) { if ((B[i] > B[i + 1]) && (m > 0))
{ bf = B[i]; B[i] = B[i - 1]; B[i - 1] = bf; }
if ((B[i] < B[i - 1]) && (m < 0))
{ bf = B[i]; B[i] = B[i - 1]; B[i - 1] = bf; } }
m = -m; }
}
Хотя эта сортировка является улучшением пузырькового метода, ее нельзя рекомендовать для частого использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов.
Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.
Программа сравнения сортировок
Пример. Определить количество временных тактов, которые требуются на сортировку с использованием метода пузырька и шейкерной сортировки.
#include <ctime> // для clock()
#include <iostream>
using namespace std;
Void BubbleSort(int *a, int n)
{ int c, i, j, k;
for (i = 0; i < N; i++)
{ for (j = 0; j < N - 1; j++)
{ k = j + 1; c = A[k];
if (A[j] > A[k]) { A[k] = A[j]; A[j] = c; }
}
}
}
Void ShakerSort(int *b, int Start, int n)
{ int Lt, Rt, i, t; Lt = Start; Rt = N - 1;
while (Lt <= Rt)
{ for (i = Rt; i >= Lt; i--)
if (B[i - 1] > B[i])
{ t = B[i]; B[i] = B[i - 1]; B[i - 1] = t; }
Lt++;
for (i = Lt; i <= Rt; i++)
if (B[i - 1] > B[i])
{ t = B[i]; B[i] = B[i - 1]; B[i - 1] = t; }
Rt--;
}
}
Void main()
{ setlocale (LC_CTYPE, "Russian");
const int N = 30000; int A[N], B[N];
clock_t t1, t2;
srand((unsigned)time(NULL));
for (int n = 10000; n <= N; n += 10000)
{ for (int i = 0; i < n; i++)
{ A[i] = rand()%999;
B[i] = A[i];
}
cout <<"n = " <<n <<endl;
cout << "Сортировка 'Пузырек'. ";
t1 = clock();
BubbleSort(A, N);
t2 = clock();
cout <<"Прошло "<<t2-t1 <<" тактов времени" <<endl;
cout <<"n = " <<n <<endl;
cout << "Шейкерная сортировка. ";
t1 = clock();
ShakerSort(B, 1, N);
t2 = clock();
cout <<"Прошло "<<t2-t1 <<" тактов времени" <<endl;
}
}
