/*/////////////////////////////////////////////////////////////////////////////
** В первой программе провести сравнение указанных алгоритмов сортировки массивов, содержащих n1, n2, n3 и n4 элементов.
** Каждую функцию сортировки вызывать трижды: для сортировки упорядоченного массива,
** массива, упорядоченного в обратном порядке,
** неупорядоченного массива.
** Сортируемая последовательность для всех методов должна быть одинаковой (сортировать копии одного массива).
** Оценить эффективность алгоритмов сортировки по заданному критерию.
**
** Порядок: по возрастанию элементов.
** Методы: шейкерная,
** Шелла (шаг сортировки задается числами Фибоначчи),
** быстрая сортировка (нерекурсивный метод и qsort()).
**
** N1 = 500, N2 = 1000, N3 = 2000, N4 = 3500.
** Критерий – время сортировки.
** Массив указателей на функции - Сортировок и Заполнений
*//////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
/*////////////////////////////////////////////
** //
** Вспомогателыные функции для алгоритмов //
** //
*/////////////////////////////////////////////
//****************************************//
void Pause(void)
{
char b;
cout<< "Нажмите ESC для продолжения\n";
while(1){
cin >> b;
if(b == 27) break;
}
}
/*
** Функция сравнения для qsort
*/
int compare(const void * x1, const void * x2)
{
return ( *(int*)x1 - *(int*)x2 ); // если результат вычитания равен 0, то числа равны, < 0: x1 < x2; > 0: x1 > x2
}
/*
** Вычисление факториала
*/
int* Fib(int Merge, int *N)
{
int oldValue = 0;
int value = 1;
int hold;
int count = 0;
/* Определяем количество элементов массива */
while(value < Merge)
{
hold = value;
value += oldValue;
oldValue = hold;
count++;
}
value = 1;
oldValue = 0;
int arr[count - 1];
/* Заполняем массив */
for(int i = 0; i < count - 1; i++)
{
hold = value;
value += oldValue;
oldValue = hold;
arr[i] = value;
}
*N = count - 1;
return arr;
}
/*////////////////////////////////////////////
** //
** Реализация алгоритмов сортировки //
** //
*/////////////////////////////////////////////
/*
** Шейкерная сортировка
*/
int ShakerSort (int *a, int n)
{
int j, k = n-1, left = 1, right = n-1, x;
int time;
time = clock();
do
{
for (j = right; j >= left; j--)
if (a[j-1] > a[j])
{
x = a[j-1];
a[j-1] = a[j];
a[j] = x;
k = j;
}
left = k+1;
for (j = left; j <= right; j++)
if (a[j-1] > a[j])
{
x = a[j-1];
a[j-1] = a[j];
a[j] = x;
k = j;
}
right = k-1;
}
while (left < right);
time = clock() - time;
return time;
}
/*
** Метод Шелла
*/
int ShellSort(int *arr, int N)
{
int i, j, m, temp, t;
unsigned int time = 0;
int * step = Fib(N/2, &t); // Массив Чисел Фибоначи
time = clock();
for (m = 0; m < t; m++)
{
for (i = step[m]; i < N; i++)
{
temp = arr[i];
j = i - step[m];
while (temp < arr[j] && j >= 0)
{
arr[j + step[m]] = arr[j];
j -= step[m];
}
arr[j + step[m]] = temp;
}
}
time = clock() - time;
return time;
}
/*
** Быстрая сортировка (нерекурсивный метод)
*/
int QuiqSort(int *arr, int N)
{
struct stack { int left; int right;} st[N/4]; // Задаем вспомогательный стек
int i, j, k, vsp, s, l, r;
unsigned int time;
s = 1;
st[1].left = 0;
st[1].right = N - 1;
time = clock();
do
{
l = st[s].left;
r = st[s].right;
s--;
do
{
i = l;
j = r;
vsp = arr[(l+r)/2];
do
{
while(arr[i] < vsp)
i++;
while(vsp < arr[j])
j--;
if(i <= j)
{
k = arr[i];
arr[i] = arr[j];
arr[j] = k;
i++;
j--;
}
}while(i < j);
if(i < r)
{
s++;
st[s].left = i;
st[s].right = r;
}
r = j;
}while(l < r);
}while(s);
time = clock() - time;
return time;
}
/*
** Сортировка qsort
*/
int qSort(int *arr, int N)
{
int left;
unsigned int time;
time = clock();
qsort(arr, N, sizeof(int), compare);
time = clock() - time;
return time;
}
/*
** Возрастание
*/
void Increase(int *arr, int N)
{
for(int i = 0; i < N; i++)
arr[i] = i*2;
}
/*
** Убывание
*/
void Discrease(int *arr, int N)
{
int count = N;
for(int i = 0; i < N; i++)
arr[i] = count--;
}
/*
** Рандом
*/
void Rand(int *arr, int N)
{
srand(time(0));
for(int i = 0; i < N; i++)
arr[i] = rand()%5000;
}
/*
** Копирование массива
*/
void Copy(int *arr,int *arr2, int N)
{
for(int i = 0; i < N; i++)
arr2[i] = arr[i];
}
int main()
{
int count = 0;
int numb[4] = {5000, 10000, 20000, 35000};
int *arr;
int *arr2;
int TimeArray[4][3][4];
/* Массив слов */
char Type[3][30] = {"Рандом ", "Убывание ", "Возрастание "};
char Func[4][50] = {"qsort ", "QuiqSort ", "ShellSort ", "ShakerSort "};
void (*pFuncType[3]) (int *, int ) = {Rand, Discrease, Increase};
int (*pFuncSort[4]) (int *, int ) = {qSort, QuiqSort, ShellSort, ShakerSort};
/* Разные размеры */
for(int i = 0; i < 4; i++)
{
arr = new int[numb[i]];
arr2 = new int[numb[i]];
/* Разные типы массивов */
for(int j = 0; j < 3; j++)
{
pFuncType[j](arr, numb[i]);
/* Разные сортировки */
for(int k = 0; k < 4; k++)
{
Copy(arr, arr2, numb[i]);
TimeArray[i][j][k] = pFuncSort[k](arr2, numb[i]);
}
}
delete [] arr;
delete [] arr2;
}
/* Вывод массива */
for(int i = 0; i < 4; i++)
{
cout << "---------------------------" << endl;
cout << "РАЗМЕР:" << numb[i] << endl;
cout << "---------------------------" << endl;
/* Разные типы массивов */
for(int j = 0; j < 3; j++)
{
cout << "** Тип " << Type[j] << endl;
cout << " ----" << endl;
/* Разные сортировки */
for(int k = 0; k < 4; k++)
cout << " * Метод: " << Func[k] << " - "<< TimeArray[i][j][k] << " млс" << endl;
cout << endl;
}
}
return 0;
}