/*/////////////////////////////////////////////////////////////////////////////
Порядок: по убыванию элементов. Методы: пузырька, шейкера, быстрая сортировка (нерекурсивный и рекурсивный методы).
N1=1000, N2=1800, N3=10000, N4=50000.
Критерий – количество перестановок.
*//////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <cstdlib>
using namespace std;
int QuickSortRecur (int * a, int N)
{
int x, w, i, j;
int col = 0;
x = a[N/2];
i = 0;
j = N-1;
do
{
while (a[i] < x)
i++;
while (x < a[j])
j--;
if (i <= j)
{
w = a[i];
a[i] = a[j];
a[j] = w;
i++;
j--;
col++;
}
}
while (i < j);
if (j > 0)
col += QuickSortRecur(a, j+1);
if (i < N-1)
col += QuickSortRecur(a + i, N-i);
return col;
}
int BubbleSort(int * a, int N)
{
int col = 0;
int i, j, x;
for (i = 1; i < N; i++)
for (j = N-1; j >= i; j--)
if (a[j-1] > a[j])
{
x = a[j-1];
a[j-1] = a[j];
a[j] = x;
col++;
}
return col;
}
int ShakerSort (int *a, int n)
{
int j, k = n-1, left = 1, right = n-1, x;
int col = 0;
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;
col++;
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;
col++;
}
right = k-1;
}
while (left < right);
return col;
}
int QuiqSort(int *arr, int N)
{
struct stack { int left; int right;} st[N/4];
int i, j, k, vsp, s, l, r;
int col = 0;
s = 1;
st[1].left = 0;
st[1].right = N - 1;
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;
col++;
i++;
j--;
}
}while(i < j);
if(i < r)
{
s++;
st[s].left = i;
st[s].right = r;
}
r = j;
}while(l < r);
}while(s);
return col;
}
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] = {1000, 1800, 10000, 50000};
int *arr;
int *arr2;
int TimeArray[4][3][4];
/* Массив слов */
char Type[3][30] = {"Рандом ", "Убывание ", "Возрастание "};
char Func[4][50] = {"QuiqSort ", "ShakerSort ", "BubbleSort ", "QuickSortRecur "};
void (*pFuncType[3]) (int *, int ) = {Rand, Discrease, Increase};
int (*pFuncSort[4]) (int *, int ) = {QuiqSort, ShakerSort, BubbleSort, QuickSortRecur};
/* Разные размеры */
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;
}