include iostream include stdlib include windows include stdio include

#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;
}