/*
Методы: пузырька, шейкера, быстрая сортировка (нерекурсивный и рекурсивный методы).
N1=1000, N2=1800, N3=10000, N4=50000.
Критерий – количество перестановок.
*/
#include <iostream>
#include <cstdlib>
using namespace std;
int QuickSortRecur (int * arr, int N)//быстрая реккурсивная сортировка
{
int somesht, fkall, i, j;
int amount = 0;
somesht = arr[N/2];
i = 0;
j = N-1;
do
{
while (arr[i] < somesht)
i++;
while (somesht < arr[j])
j--;
if (i <= j)
{
amount++;
fkall = arr[i];
arr[i] = arr[j];
arr[j] = fkall;
i++;
j--;
}
} while (i < j);
if (j > 0)
amount += QuickSortRecur(arr, j+1);
if (i < N-1)
amount += QuickSortRecur(arr + i, N-i);
return amount;
}
int BubbleSort(int * arr, int N)//сортировка пузырьком
{
int amount = 0;
int i, j, somesht;
for (i = 1; i < N; i++)
for (j = N-1; j >= i; j--)
if (arr[j-1] < arr[j])
{
amount++;
somesht = arr[j];
arr[j] = arr[j-1];
arr[j-1] = somesht;
}
return amount;
}
int ShakerSort (int *arr, int n)//шейкерная сортировка
{
int j, kek = n-1, left = 1, right = n - 1, somesht;
int amount = 0;
do
{
for (j = right; j >= left; j--)// Просматриваем справа налево
if (arr[j-1] < arr[j])
{
amount++;
somesht = arr[j];
arr[j] = arr[j-1];
arr[j-1] = somesht;
kek = j;
}
left = kek+1;
for (j = left; j <= right; j++)// теперь слева направо
if (arr[j-1] < arr[j])
{
amount++;
somesht = arr[j];
arr[j] = arr[j-1];
arr[j-1] = somesht;
kek = j;
}
right = kek-1;
}
while (right > left);
return amount;
}
int QuiqSort(int *arr, int N)//быстрая нереккурсивная сортировка
{
struct stack { int left; int right;} idgf[N/4];
int i, j, kek, nuttin, s, lol, idk;
int amount = 0;
s = 1;
idgf[1].left = 0;
idgf[1].right = N - 1;
do
{
lol = idgf[s].left;
idk = idgf[s].right;
s--;
do
{
i = lol;
j = idk;
nuttin = arr[(lol+idk)/2];
do
{
while(arr[i] < nuttin)
i++;
while(nuttin < arr[j])
j--;
if(i <= j)
{
amount++;
kek = arr[i];
arr[i] = arr[j];
arr[j] = kek;
i++;
j--;
}
}while(i < j);
if(i < idk)
{
s++;
idgf[s].left = i;
idgf[s].right = idk;
}
idk = j;
}while(lol < idk);
}while(s);
return amount;
}
void Increase(int *arr, int N)
{
int count = 0;
for(int i = 0; i < N; i++)
arr[i] = count++;
}
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(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()
{
setlocale(LC_ALL, "Rus");
int numb[4] = {1000, 1800, 10000, 50000};
int *arr;
int *arr2;
int JustArray[4][3][4];
int amount;
//Массив слов
char Type[3][30] = {"Рандом ", "Убывание ", "Возрастание "};
char Func[4][50] = {"QuiqSort ", "ShakerSort ", "BubbleSort ", "QuickSortRecur "};
void (*pointType[3]) (int *, int ) = {Rand, Discrease, Increase};
int (*pointSort[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++)
{
pointType[j](arr, numb[i]);
//Разные сортировки
for(int kek = 0; kek < 4; kek++)
{
Copy(arr, arr2, numb[i]);
JustArray[i][j][kek] = pointSort[kek](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 kek = 0; kek < 4; kek++)
cout << "Метод: " << Func[kek] << " - "<< amount << " перестановок" << endl;
cout << endl;
}
}
return 0;
}