#include <iostream>
#include <stdlib.h>
#include <windows.h>
#include <stdio.h>
#include <ctime>
int Kol=0;
void Swap(int *mas, int i,int j )
{
int temp=mas[i];
mas[i]=mas[j];
mas[j]=temp;
Kol+=3;
};
using namespace std;
class Massiv
{
public:
int N;
int *MassSort, *MassSortBack, *Mass;
Massiv (int n) // Просто конструктор
{
N=n;
Mass=new int[N];
MassSort=new int[N]; // Выделяем память
MassSortBack=new int[N];
for (int i=0;i<N;++i)
{
Mass[i]=rand(); // Cлучайные числа
MassSort[i]=i+1; // Натуральный ряд
MassSortBack[i]=N-i;
}
}
Massiv( Massiv &A) // Конструктор копирования
{
N=A.N;
Mass=new int[N]; // Выделение памяти
MassSort=new int[N];
MassSortBack=new int[N];
for (int i=0;i<N;++i)
{
Mass[i]=A.Mass[i]; // Копирование массивов
MassSort[i]=A.MassSort[i];
MassSortBack[i]=A.MassSortBack[i];
}
}
~Massiv() // Деструктор
{
delete [] MassSort;
delete [] MassSortBack;
delete [] Mass;
}
void Vibor(int*) ;// Сортировка выбором
void ShakerSort(int*) ;// Шейкерная сортировка
void SiftDown(int*, int, int) ; // Сортировка пирамидой (состоит из 2-х функций)
void HeapSort(int*) ;
void Qsort (int*, int, int) ; //Быстрая сортировка
};
void Massiv::Vibor(int *Mas) // Сортировка выбором
{
int temp, i, j, min;
for ( i=0; i <N-1; i++)
{
Kol++;
min = i;
for ( j=i+1; j<N; j++)
{
if (Mas[j] < Mas[min])
{
min = j;
Kol++;
}
}
if(min!=i)
Swap(Mas,i,min);
}
}
void Massiv::ShakerSort(int *Mas) // Шейкерная сортировка
{
int Left, Right, i;
Left=1;
Right=N-1;
while (Left<=Right)
{
for (i=Right; i>=Left; i--)
if (Mas[i-1]>Mas[i])
Swap(Mas, i, i-1);
Left++;
for (i=Left; i<=Right; i++)
if (Mas[i-1]>Mas[i])
Swap(Mas, i, i-1);
Right--;
}
}
void Massiv::SiftDown(int *Mas, int root, int bottom) // Сортировка пирамидой (состоит из 2-х функций)
{
int done, maxChild, temp;
done = 0;
while ((root*2 <= bottom) && (!done))
{
if (root*2 == bottom)
maxChild = root * 2;
else
if (Mas[root * 2] > Mas[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
Kol++;
if (Mas[root] < Mas[maxChild])
{
temp = Mas[root];
Mas[root] = Mas[maxChild];
Mas[maxChild] = temp;
root = maxChild;
Kol+=4;
}
else
done = 1;
}
}
void Massiv::HeapSort(int *Mas)
{
int i, temp;
for (i = (N / 2)-1; i >= 0; i--)
SiftDown(Mas, i, N);
for (i = N-1; i >= 1; i--)
{
Swap(Mas, 0, i);
SiftDown(Mas, 0, i-1);
}
}
void Massiv::Qsort (int *Mas, int b, int e) //Быстрая сортировка
{
int l=b, r=e;
int piv=Mas[(l+r)/2]; // Опорным элемент - средний
while (l <= r)
{
while (Mas[l]<piv)
l++;
while (Mas[r]>piv)
r--;
if (l<=r)
if(l!=r)
Swap(Mas, l++, r--);
else
{
r--;
l++;
}
}
if (b < r)
Qsort (Mas, b, r);
if (e > l)
Qsort (Mas, l, e);
}
int main()
{
setlocale(LC_ALL, "Russian");
srand(time(NULL));
//тестируем сортировки
Massiv a(10);
cout<<"ТЕСТИРУЕМ СОРТИРОВКИ:"<<endl;
cout<<"до сортировки: "<<endl;
Massiv F(a);
for (int i=0;i<10;++i)
cout<<F.Mass[i]<<" ";
cout<<endl<<"после сортировки методом выбора: "<<endl;
F.Vibor(F.Mass);
for (int i=0;i<10;++i)
cout<<F.Mass[i]<<" ";
cout<<endl<<"до сортировки: "<<endl;
Massiv FF(a);
for (int i=0;i<10;++i)
cout<<FF.Mass[i]<<" ";
cout<<endl<<"после шейкерной сортировки : "<<endl;
FF.ShakerSort(FF.Mass);
for (int i=0;i<10;++i)
cout<<FF.Mass[i]<<" ";
cout<<endl<<"до сортировки: "<<endl;
Massiv FFF(a);
for (int i=0;i<10;++i)
cout<<FFF.Mass[i]<<" ";
cout<<endl<<"после пирамидальной сортировки : "<<endl;
FFF.HeapSort(FFF.Mass);
for (int i=0;i<10;++i)
cout<<FFF.Mass[i]<<" ";
cout<<endl<<"до сортировки: "<<endl;
Massiv FFFF(a);
for (int i=0;i<10;++i)
cout<<FFFF.Mass[i]<<" ";
cout<<endl<<"после быстрой сортировки : "<<endl;
FFFF.Qsort(FFFF.Mass, 0, 9);
for (int i=0;i<10;++i)
cout<<FFFF.Mass[i]<<" ";
cout<<endl;
int N[4]={500,1000,2000,3500};
int K[3]={0,0,0}; // для подсчета количества перестановок
for(int i=0; i<4; i++)
{
Kol=0;
cout<<endl<<" для массива из "<<N[i]<<" элементов:"<<endl;
Massiv A(N[i]); // создаем массив нужной длинны
Massiv B(A); // копия массива для сортировки
// сортировка методом выбора
B.Vibor(B.Mass);
K[0]=Kol;
Kol=0;
B.Vibor(B.MassSort);
K[1]=Kol;
Kol=0;
B.Vibor(B.MassSortBack);
K[2]=Kol;
Kol=0;
cout<<"\n +--------------+-----------+-----------+---------------+\n";
cout<<" | | rand mass | sort mass | sortback mass |\n";
cout<<" +--------------+-----------+-----------+---------------+\n";
cout<<" | vibor(select)|";
printf(" %9d | %9d | %13d | ", K[0], K[1], K[2]);
Massiv C(A);
C.ShakerSort(C.Mass);
K[0]=Kol;
Kol=0;
C.ShakerSort(C.MassSort);
K[1]=Kol;
Kol=0;
C.ShakerSort(C.MassSortBack);
K[2]=Kol;
Kol=0;
cout<<"\n +--------------+-----------+-----------+---------------+\n";
cout<<" | ShakerSort |";
printf(" %9d | %9d | %13d | ", K[0], K[1], K[2]);
cout<<"\n +--------------+-----------+-----------+---------------+\n";
Massiv D(A);
D.HeapSort(D.Mass);
K[0]=Kol;
Kol=0;
D.HeapSort(D.MassSort);
K[1]=Kol;
Kol=0;
D.HeapSort(D.MassSortBack);
K[2]=Kol;
Kol=0;
cout<<" | Piramida |";
printf(" %9d | %9d | %13d | ", K[0], K[1], K[2]);
cout<<"\n +--------------+-----------+-----------+---------------+\n";
Massiv E(A);
E.Qsort(E.Mass, 0, N[i]-1);
K[0]=Kol;
Kol=0;
E.Qsort(E.MassSort, 0, N[i]-1);
K[1]=Kol;
Kol=0;
E.Qsort(E.MassSortBack, 0, N[i]-1);
K[2]=Kol;
Kol=0;
cout<<" | Qsort |";
printf(" %9d | %9d | %13d | ", K[0], K[1], K[2]);
cout<<"\n +--------------+-----------+-----------+---------------+\n";
}
return 0;
}