All sorting algorithms in one class

//Класс содержащий все сортировки, которые тебе нужны:пузырек, вставка, быстрая, слияние и т.д.
//Это заголовочный:













#include <vector>
using std::vector;

#ifndef CLASSES
#define CLASSES


class SortByBubble{
    friend void quickSort(int* arrayForSort, int right);
    friend void quickSortplusMedian(int* arrayForSort, int right);
    friend void quickSortplusInsertion(int* arrayForSort, int right);
    friend void ultraQuickSort(int* arrayForSort, int right);
    friend void insertion(int* arrayForSort, int right);
    friend void mergeSort(int* arrayForSort, int size);



    const int sizeOfVector;
    const int numberOfVectors;
    bool  isAscending;
    int **sameVectors;
    int **bufferForVectors;
    int **sortedVectors;
public:
    SortByBubble(int vectorSize, int NumberOfVectors, bool isAscend);
    SortByBubble(int vectorSize, int NumberOfVectors, bool isAscend,int lb,int rb);
    ~SortByBubble();
    double bubbleTime();
    double choiceTime();
    double insertTime();
    double shellShellTime(); //using original Shell sequence
    double shellShellTime2();
    double shellA102549Time(); //using A102549 sequence. It's well known sequence, don't you know???
    double shellHibbardTime(); //using Hibbard sequence. all i:(2^i-1)<=N
    double shellDeuce();
    double hibbard();
    double ciura();
    double shellDeuceWithOutput();
    double hibbardWithOutput();
    double ciuraWithOutput();
    double insert();
    double quickSortTime();
    double quickSortplusInsertionTime();//must be better on 20%
    double quickSortplusMedianTime();//must be better on 5%
    double ultraQuickSortTime();//25%
    double heapSortTime();
    double mergeSortTime();
    void heapify(int firstIndex, int secondIndex, int length);
    void makeHeap();
    void printUnsort2txt();
    void printSort2txt();
};

#endif /*CLASSES*/











//ЭТО РЕАЛИЗАЦИЯ КЛАССА.

















#include "Classes.h"
#include <ctime>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cstdlib>

using std::swap;
using std::endl;
using std::setw;
using std::ctime;
using std::srand;
using std::pow;
using std::printf;

//SortByBubble::SortByBubble(int vSize = 10, int nVectors = 10, bool isAscend = true):
//  sizeOfVector(vSize),
//  numberOfVectors(nVectors)
//{
//  srand(time(NULL));
//  sameVectors = new int*[nVectors];
//  bufferForVectors = new int*[nVectors];
//  sortedVectors = new int*[nVectors];
//  for(int i=0;i<nVectors;i++){
//      sameVectors[i] = new int[vSize];
//      bufferForVectors[i] = new int[vSize];
//      sortedVectors[i] = new int[vSize];
//      for(int j=0;j<vSize;j++){
//          sameVectors[i][j] = j;
//          bufferForVectors[i][j] = sameVectors[i][j];
//      }
//  }
//}

bool errflag = 0;
SortByBubble::SortByBubble(int vSize = 10, int nVectors = 10, bool isAscend = true, int lb = 1, int rb = 100):
    sizeOfVector(vSize),
    numberOfVectors(nVectors)
{
    srand(time(NULL));
    sameVectors = new int*[nVectors];
    bufferForVectors = new int*[nVectors];
    sortedVectors = new int*[nVectors];
    for(int i=0;i<nVectors;i++){
        sameVectors[i] = new int[vSize];
        bufferForVectors[i] = new int[vSize];
        sortedVectors[i] = new int[vSize];
        for(int j=0;j<vSize;j++){
            sameVectors[i][j] = rand()%(rb -lb +1)+lb;
            bufferForVectors[i][j] = sameVectors[i][j];
        }
    }
}
SortByBubble::~SortByBubble(){
    for(int i = 0; i<numberOfVectors;i++){
        delete[] sortedVectors[i];
        delete[] sameVectors[i];
        delete[] bufferForVectors[i];
    }
    delete[] sortedVectors;
    delete[] sameVectors;
    delete[] bufferForVectors;
}

//print unsorted and sorted arrays in file
void SortByBubble::printUnsort2txt(){
    std::ofstream output("unsortarray.txt");
    for(int j=0;j<numberOfVectors;j++){
        output<<"\n***** "<<j<<" *****\n\n";
        for(int i=0;i<sizeOfVector;i++){
            output<<setw(6)<<sameVectors[j][i];
            //if((i!=0)&&(i%20 == 19)) output<<endl;
        }
        output<<endl;
    }
    output.close();
}
void SortByBubble::printSort2txt(){
    std::ofstream output("sortarray.txt");
    if(errflag) output<<"\nERROR\n";
    for(int j=0;j<numberOfVectors;j++){
        output<<"\n***** "<<j<<" *****\n\n";
        for(int i=0;i<sizeOfVector;i++){
            output<<setw(6)<<sortedVectors[j][i];
            //if((i!=0)&&(i%20 == 19)) output<<endl;
        }
        output<<endl;
    }
    output.close();
}
//simple sorts
double SortByBubble::bubbleTime(){
    time_t start;
    time_t stop;
    double bubbleTime=0;
    for(int j=0;j<numberOfVectors;j++){
        time(&start);
        bool flag = 1;
        while(flag){
            bool fflag = 0;
            for(int i=0;i<sizeOfVector-1;i++){
                if(sameVectors[j][i]>sameVectors[j][i+1]){
                    int t = sameVectors[j][i];
                    sameVectors[j][i] = sameVectors[j][i+1];
                    sameVectors[j][i+1] = t;
                    fflag = 1;
                }
            }
            if(fflag==0) flag=0;
        }
        time(&stop);
        bubbleTime += difftime(stop, start);
        //Check errors.
        for(int i = 0;i<sizeOfVector-1;i++){
            if(sameVectors[j][i]>sameVectors[j][i+1]){
                errflag = true;
            }
        }
    }

    for(int i = 0; i<numberOfVectors;i++){
        for(int j = 0 ; j<sizeOfVector; j++){
            sortedVectors[i][j] = sameVectors[i][j];
            sameVectors[i][j] = bufferForVectors[i][j];
        }
    }
    return bubbleTime/numberOfVectors;
}
double SortByBubble::choiceTime(){
    time_t start;
    time_t stop;
    double choiceTime=0;
    for(int k = 0;k<numberOfVectors;k++){

        time(&start);
        for(int i=0;i<sizeOfVector-1;i++){
            int min = i;
            for(int j=i+1;j<sizeOfVector;j++){
                if(sameVectors[k][min]>sameVectors[k][j]){
                    min = j;
                }
            }
            if(min!=i){
                int t = sameVectors[k][min];
                sameVectors[k][min] = sameVectors[k][i];
                sameVectors[k][i] = t;
            }
        }
        time(&stop);
        choiceTime+=difftime(stop,start);
        //Check errors.
        for(int i = 0;i<sizeOfVector-1;i++){
            if(sameVectors[k][i]>sameVectors[k][i+1]){
                errflag = true;
            }
        }
    }
    for(int i = 0; i<numberOfVectors;i++){
        for(int j = 0 ; j<sizeOfVector; j++){
            sortedVectors[i][j] = sameVectors[i][j];
            sameVectors[i][j] = bufferForVectors[i][j];
        }
    }
    return choiceTime/numberOfVectors;
}
double SortByBubble::insertTime(){
    time_t start;
    time_t stop;
    double insertTime = 0;

    for(int i=0;i<numberOfVectors;i++){
        time(&start);

        for(int j=1;j<sizeOfVector;j++){
            int current = sameVectors[i][j];
            int k = j;
            while((k>0)&&(sameVectors[i][k-1]>current)){
                sameVectors[i][k] = sameVectors[i][k-1];
                k--;
            }
            sameVectors[i][k] = current;
        }
        time(&stop);
        insertTime += difftime(stop,start);
        //Check errors.
        for(int k = 0;k<sizeOfVector-1;k++){
            if(sameVectors[i][k]>sameVectors[i][k+1]){
                errflag = true;
            }
        }
    }
    for(int i = 0; i<numberOfVectors;i++){
        for(int j = 0 ; j<sizeOfVector; j++){
            sortedVectors[i][j] = sameVectors[i][j];
            sameVectors[i][j] = bufferForVectors[i][j];
        }
    }
    return insertTime/numberOfVectors;
}
//just work. very fast. i don't know why
double SortByBubble::shellDeuce(){
    time_t start;
    time_t stop;
    double shellTime = 0;

    int step[20];
    for(int i = 0;i<20;i++) step[i] = pow(2,i);

    int l = 19;
    while(step[l]>sizeOfVector) l--;
    int buff = l;
    for(int j = 0; j<numberOfVectors;j++){
        time(&start);

        for(l = buff;l>=0;l--){
            int gap = step[l];
            for(int i = gap;i<sizeOfVector;i++){
                int temp = sameVectors[j][i];
                int k;
                for(k = i; (k>=gap)&&(sameVectors[j][k-gap]>temp);k-=gap){
                    sameVectors[j][k] = sameVectors[j][k-gap];
                }
                sameVectors[j][k] = temp;
            }
        }
        time(&stop);
        shellTime +=difftime(stop,start);
        //Check errors.
        for(int i = 0;i<sizeOfVector-1;i++){
            if(sameVectors[j][i]>sameVectors[j][i+1]){
                errflag = true;
            }
        }
    }

    for(int i = 0; i<numberOfVectors;i++){
        for(int j = 0 ; j<sizeOfVector; j++){
            sortedVectors[i][j] = sameVectors[i][j];
            sameVectors[i][j] = bufferForVectors[i][j];
        }
    }
    return shellTime/numberOfVectors;
}
double SortByBubble::hibbard(){
    time_t start;
    time_t stop;
    double shellTime = 0;

    int step[20];
    for(int i = 1;i<=20;i++) step[i-1] = (pow(2,i)-1);

    int l = 19;
    while(step[l]>sizeOfVector) l--;
    int buff = l;

    for(int j = 0; j<numberOfVectors;j++){
        time(&start);

        for(l = buff;l>=0;l--){
            int gap = step[l];
            for(int i = gap;i<sizeOfVector;i++){
                int temp = sameVectors[j][i];
                int k;
                for(k = i; (k>=gap)&&(sameVectors[j][k-gap]>temp);k-=gap){
                    sameVectors[j][k] = sameVectors[j][k-gap];
                }
                sameVectors[j][k] = temp;
            }
        }

        time(&stop);
        shellTime +=difftime(stop,start);
        //Check errors.
        for(int i = 0;i<sizeOfVector-1;i++){
            if(sameVectors[j][i]>sameVectors[j][i+1]){
                errflag = true;
            }
        }

    }

    for(int i = 0; i<numberOfVectors;i++){
        for(int j = 0 ; j<sizeOfVector; j++){
            sortedVectors[i][j] = sameVectors[i][j];
            sameVectors[i][j] = bufferForVectors[i][j];
        }
    }
    return shellTime/numberOfVectors;
}
double SortByBubble::ciura(){
    time_t start;
    time_t stop;
    double shellTime = 0;

    int step[] = {1, 4, 10, 23, 57, 132, 301, 701, 1750};

    int l = 8;
    while(step[l]>sizeOfVector) l--;
    int buff = l;
    for(int j = 0; j<numberOfVectors;j++){
        time(&start);

        for(l = buff;l>=0;l--){
            int gap = step[l];
            for(int i = gap;i<sizeOfVector;i++){
                int temp = sameVectors[j][i];
                int k;
                for(k = i; (k>=gap)&&(sameVectors[j][k-gap]>temp);k-=gap){
                    sameVectors[j][k] = sameVectors[j][k-gap];
                }
                sameVectors[j][k] = temp;
            }
        }
        time(&stop);
        shellTime +=difftime(stop,start);
        //Check errors.
        for(int i = 0;i<sizeOfVector-1;i++){
            if(sameVectors[j][i]>sameVectors[j][i+1]){
                errflag = true;
            }
        }
    }

    for(int i = 0; i<numberOfVectors;i++){
        for(int j = 0 ; j<sizeOfVector; j++){
            sortedVectors[i][j] = sameVectors[i][j];
            sameVectors[i][j] = bufferForVectors[i][j];
        }
    }
    return shellTime/numberOfVectors;
}
//work. Print every step in file
double SortByBubble::shellDeuceWithOutput(){
    std::ofstream output("shellDeuceEveryStep.txt");
    time_t start;
    time_t stop;
    double shellTime = 0;

    int step[20];
    for(int i = 0;i<20;i++) step[i] = pow(2,i);

    int l = 19;
    while(step[l]>sizeOfVector) l--;
    int buff = l;
    for(int j = 0; j<numberOfVectors;j++){
        output<<"\n*****"<<j<<"*****\n";

        time(&start);
        for(int y=0;y<sizeOfVector;y++){
                    output<<setw(4)<<sameVectors[j][y];
                }
                output<<endl;
        for(l = buff;l>=0;l--){
            int gap = step[l];
            output<<"GAP - "<<gap<<endl;
            for(int i = gap;i<sizeOfVector;i++){
                int temp = sameVectors[j][i];
                int k;
                for(k = i; (k>=gap)&&(sameVectors[j][k-gap]>temp);k-=gap){
                    sameVectors[j][k] = sameVectors[j][k-gap];
                }
                sameVectors[j][k] = temp;
                for(int y=0;y<sizeOfVector;y++){
                    output<<setw(4)<<sameVectors[j][y];
                }
                output<<endl;
            }
        }
        time(&stop);
        shellTime +=difftime(stop,start);
        //Check errors.
        for(int i = 0;i<sizeOfVector-1;i++){
            if(sameVectors[j][i]>sameVectors[j][i+1]){
                errflag = true;
            }
        }
    }

    for(int i = 0; i<numberOfVectors;i++){
        for(int j = 0 ; j<sizeOfVector; j++){
            sortedVectors[i][j] = sameVectors[i][j];
            sameVectors[i][j] = bufferForVectors[i][j];
        }
    }
    output.close();
    return shellTime/numberOfVectors;
}
double SortByBubble::hibbardWithOutput(){
    std::ofstream output("shellHibbardEveryStep.txt");
    time_t start;
    time_t stop;
    double shellTime = 0;

    int step[20];
    for(int i = 1;i<=20;i++) step[i-1] = (pow(2,i)-1);

    int l = 19;
    while(step[l]>sizeOfVector) l--;
    int buff = l;

    for(int j = 0; j<numberOfVectors;j++){
        time(&start);
        output<<"\n*****"<<j<<"*****\n";
        for(int y=0;y<sizeOfVector;y++){
                    output<<setw(4)<<sameVectors[j][y];
                }
                output<<endl;
        for(l = buff;l>=0;l--){
            int gap = step[l];
            output<<"GAP - "<<gap<<endl;
            for(int i = gap;i<sizeOfVector;i++){
                int temp = sameVectors[j][i];
                int k;
                for(k = i; (k>=gap)&&(sameVectors[j][k-gap]>temp);k-=gap){
                    sameVectors[j][k] = sameVectors[j][k-gap];
                }
                sameVectors[j][k] = temp;
                for(int y=0;y<sizeOfVector;y++){
                    output<<setw(4)<<sameVectors[j][y];
                }
                output<<endl;
            }
        }

        time(&stop);
        shellTime +=difftime(stop,start);
        //Check errors.
        for(int i = 0;i<sizeOfVector-1;i++){
            if(sameVectors[j][i]>sameVectors[j][i+1]){
                errflag = true;
            }
        }

    }

    for(int i = 0; i<numberOfVectors;i++){
        for(int j = 0 ; j<sizeOfVector; j++){
            sortedVectors[i][j] = sameVectors[i][j];
            sameVectors[i][j] = bufferForVectors[i][j];
        }
    }
    output.close();
    return shellTime/numberOfVectors;
}
double SortByBubble::ciuraWithOutput(){
    std::ofstream output("shellCiuraEveryStep.txt");
    time_t start;
    time_t stop;
    double shellTime = 0;

    int step[] = {1, 4, 10, 23, 57, 132, 301, 701, 1750};

    int l = 8;
    while(step[l]>sizeOfVector) l--;
    int buff = l;
    for(int j = 0; j<numberOfVectors;j++){
        time(&start);
        output<<"\n*****"<<j<<"*****\n";
        for(int y=0;y<sizeOfVector;y++){
                    output<<setw(4)<<sameVectors[j][y];
                }
                output<<endl;
        for(l = buff;l>=0;l--){
            int gap = step[l];
            output<<"GAP - "<<gap<<endl;
            for(int i = gap;i<sizeOfVector;i++){
                int temp = sameVectors[j][i];
                int k;
                for(k = i; (k>=gap)&&(sameVectors[j][k-gap]>temp);k-=gap){
                    sameVectors[j][k] = sameVectors[j][k-gap];
                }
                sameVectors[j][k] = temp;
                for(int y=0;y<sizeOfVector;y++){
                    output<<setw(4)<<sameVectors[j][y];
                }
                output<<endl;
            }
        }
        time(&stop);
        shellTime +=difftime(stop,start);
        //Check errors.
        for(int i = 0;i<sizeOfVector-1;i++){
            if(sameVectors[j][i]>sameVectors[j][i+1]){
                errflag = true;
            }
        }
    }

    for(int i = 0; i<numberOfVectors;i++){
        for(int j = 0 ; j<sizeOfVector; j++){
            sortedVectors[i][j] = sameVectors[i][j];
            sameVectors[i][j] = bufferForVectors[i][j];
        }
    }
    output.close();
    return shellTime/numberOfVectors;
}
double SortByBubble::quickSortTime(){
    time_t start;
    time_t stop;
    double quickSortTime=0;
    for(int k=0;k<numberOfVectors;k++){
        time(&start);

        quickSort(sameVectors[k],sizeOfVector-1);

        time(&stop);
        quickSortTime+=difftime(stop,start);
        //Check errors.
        for(int i = 0;i<sizeOfVector-1;i++){
            if(sameVectors[k][i]>sameVectors[k][i+1]){
                errflag = true;
            }
        }
    }
    sortedVectors = sameVectors;
    sameVectors = bufferForVectors;
    return quickSortTime/numberOfVectors;
}
double SortByBubble::quickSortplusInsertionTime(){
    time_t start;
    time_t stop;
    double quickSortTime=0;
    for(int k=0;k<numberOfVectors;k++){
        time(&start);

        quickSortplusInsertion(sameVectors[k],sizeOfVector-1);

        time(&stop);
        quickSortTime+=difftime(stop,start);
        //Check errors.
        for(int i = 0;i<sizeOfVector-1;i++){
            if(sameVectors[k][i]>sameVectors[k][i+1]){
                errflag = true;
            }
        }
    }
    sortedVectors = sameVectors;
    sameVectors = bufferForVectors;
    return quickSortTime/numberOfVectors;
}
double SortByBubble::quickSortplusMedianTime(){
    time_t start;
    time_t stop;
    double quickSortTime=0;
    for(int k=0;k<numberOfVectors;k++){
        time(&start);

        quickSortplusMedian(sameVectors[k],sizeOfVector-1);

        time(&stop);
        quickSortTime+=difftime(stop,start);
        //Check errors.
        for(int i = 0;i<sizeOfVector-1;i++){
            if(sameVectors[k][i]>sameVectors[k][i+1]){
                errflag = true;
            }
        }
    }
    sortedVectors = sameVectors;
    sameVectors = bufferForVectors;
    return quickSortTime/numberOfVectors;
}
double SortByBubble::ultraQuickSortTime(){
    time_t start;
    time_t stop;
    double quickSortTime=0;
    for(int k=0;k<numberOfVectors;k++){
        time(&start);

        ultraQuickSort(sameVectors[k],sizeOfVector-1);

        time(&stop);
        quickSortTime+=difftime(stop,start);
        //Check errors.
        for(int i = 0;i<sizeOfVector-1;i++){
            if(sameVectors[k][i]>sameVectors[k][i+1]){
                errflag = true;
            }
        }
    }
    sortedVectors = sameVectors;
    sameVectors = bufferForVectors;
    return quickSortTime/numberOfVectors;
}
double SortByBubble::heapSortTime(){
    time_t start;
    time_t stop;
    double heapSortTime=0;
    for(int k=0;k<numberOfVectors;k++){
        time(&start);

        for(int i = sizeOfVector/2;i>=0;i--){
            heapify(k,i,sizeOfVector);
        }

        for(int i = sizeOfVector - 1;i>0;){
            swap(sameVectors[k][i],sameVectors[k][0]);
            i--;
            heapify(k,0,i);
        }


        time(&stop);
        heapSortTime+=difftime(stop,start);
        //Check errors.
        for(int i = 0;i<sizeOfVector-1;i++){
            if(sameVectors[k][i]>sameVectors[k][i+1]){
                errflag = true;
            }
        }
    }
    sortedVectors = sameVectors;
    sameVectors = bufferForVectors;
    return heapSortTime/numberOfVectors;
}
double SortByBubble::mergeSortTime(){
    time_t start;
    time_t stop;
    double mergeSortTime=0;
    for(int k=0;k<numberOfVectors;k++){
        time(&start);

        mergeSort(sameVectors[k],sizeOfVector);

        time(&stop);
        mergeSortTime+=difftime(stop,start);
        //Check errors.
        for(int i = 0;i<sizeOfVector-1;i++){
            if(sameVectors[k][i]>sameVectors[k][i+1]){
                errflag = true;
                break;
            }
        }
        if(errflag) break;
    }
    sortedVectors = sameVectors;
    sameVectors = bufferForVectors;
    return mergeSortTime/numberOfVectors;
}

void SortByBubble::heapify(int fIndex, int sIndex, int length){
    while(true){
        int leftChild = 2*sIndex + 1;
        int rightChild = 2*sIndex + 2;
        int elder = sIndex;

        if((leftChild < length+1) && (sameVectors[fIndex][leftChild]>sameVectors[fIndex][elder])){
            elder = leftChild;
        }
        if((rightChild < length+1)&&(sameVectors[fIndex][rightChild]>sameVectors[fIndex][elder])){
            elder = rightChild;
        }
        if(elder == sIndex) break;

        swap(sameVectors[fIndex][sIndex],sameVectors[fIndex][elder]);
        sIndex = elder;
    }
}
void SortByBubble::makeHeap(){
    for(int j = 0; j<numberOfVectors;j++){

        for(int i = sizeOfVector/2;i>=0;i--){
            heapify(j,i,sizeOfVector);
        }

    }
}





void insertion(int* arr, int size){
    for(int j=1;j<size+1;j++){
            int current = arr[j];//HAAARRRRR!!!
            int k = j;
            while((k>0)&&(arr[k-1]>current)){
                arr[k] = arr[k-1];
                k--;
            }
            arr[k] = current;
    }
}
void quickSort(int* arrayForSort, int size){
    int pivot = size/2;
    int base = arrayForSort[pivot];
    int leftIterator = 0;
    int rightIterator = size;
    do{
        while(arrayForSort[leftIterator]<base)leftIterator++;
        while(arrayForSort[rightIterator]>base) rightIterator--;
        if(leftIterator<=rightIterator){
            swap(arrayForSort[leftIterator],arrayForSort[rightIterator]);
            leftIterator++;
            rightIterator--;
        }
    }while(leftIterator<=rightIterator);
    if(rightIterator>0) quickSort(arrayForSort, rightIterator);
    if(size>leftIterator) quickSort(arrayForSort+leftIterator, size-leftIterator);
}
void quickSortplusInsertion(int *arrayForSort, int size){
    if(size<25){
        insertion(arrayForSort,size);
        return;
    }
    int pivot = size/2;
    int base = arrayForSort[pivot];
    int leftIterator = 0;
    int rightIterator = size;
    do{
        while(arrayForSort[leftIterator]<base)leftIterator++;
        while(arrayForSort[rightIterator]>base) rightIterator--;
        if(leftIterator<=rightIterator){
            swap(arrayForSort[leftIterator],arrayForSort[rightIterator]);
            leftIterator++;
            rightIterator--;
        }
    }while(leftIterator<=rightIterator);
    if(rightIterator>0) quickSortplusInsertion(arrayForSort, rightIterator);
    if(size>leftIterator) quickSortplusInsertion(arrayForSort+leftIterator, size-leftIterator);
}
void quickSortplusMedian(int *arrayForSort, int size){
    int pivot = (rand()%(size+1)+rand()%(size+1)+rand()%(size+1))/3;
    int base = arrayForSort[pivot];
    int leftIterator = 0;
    int rightIterator = size;
    do{
        while(arrayForSort[leftIterator]<base)leftIterator++;
        while(arrayForSort[rightIterator]>base) rightIterator--;
        if(leftIterator<=rightIterator){
            swap(arrayForSort[leftIterator],arrayForSort[rightIterator]);
            leftIterator++;
            rightIterator--;
        }
    }while(leftIterator<=rightIterator);
    if(rightIterator>0) quickSortplusMedian(arrayForSort, rightIterator);
    if(size>leftIterator) quickSortplusMedian(arrayForSort+leftIterator, size-leftIterator);
}
void ultraQuickSort(int *arrayForSort, int size){
    if(size<25){
        insertion(arrayForSort,size);
        return;
    }
    int pivot = (rand()%(size+1)+rand()%(size+1)+rand()%(size+1))/3;
    int base = arrayForSort[pivot];
    int leftIterator = 0;
    int rightIterator = size;
    do{
        while(arrayForSort[leftIterator]<base)leftIterator++;
        while(arrayForSort[rightIterator]>base) rightIterator--;
        if(leftIterator<=rightIterator){
            swap(arrayForSort[leftIterator],arrayForSort[rightIterator]);
            leftIterator++;
            rightIterator--;
        }
    }while(leftIterator<=rightIterator);
    if(rightIterator>0) ultraQuickSort(arrayForSort, rightIterator);
    if(size>leftIterator) ultraQuickSort(arrayForSort+leftIterator, size-leftIterator);
}
void mergeSort(int *forSort, int size){
    if(size>25){
        int halfSize = size/2;
        mergeSort(forSort,halfSize);
        mergeSort(forSort+halfSize,size - halfSize);
        int firstIterator = 0;
        int secondIterator = 0;
        int* tmp = new int[size];
        int i = 0;
        while(((firstIterator<halfSize)||(secondIterator<(size-halfSize)))&&(i<size)){
            if(forSort[firstIterator]>(forSort+halfSize)[secondIterator]){
                if(secondIterator>=(size - halfSize)){
                    tmp[i] = forSort[firstIterator];
                    firstIterator++;
                    i++;
                }
                else{
                    tmp[i] = (forSort+halfSize)[secondIterator];
                    secondIterator++;
                    i++;
                }
            }
            else{
                if(firstIterator>=halfSize){
                    tmp[i] = (forSort+halfSize)[secondIterator];
                    secondIterator++;
                    i++;
                }
                else{
                    tmp[i] = forSort[firstIterator];
                    firstIterator++;
                    i++;
                }
            }
        }
        /*for(int i = 0;i<size;i++){
            if(forSort[firstIterator]>(forSort+halfSize)[secondIterator]&&((firstIterator<halfSize)||(secondIterator<(size-halfSize)))){
                tmp[i] = (forSort+halfSize)[secondIterator];
                secondIterator++;
            }
            else{
                tmp[i] = forSort[firstIterator];
                firstIterator++;
            }
        }
            */
        for(i = 0;i<size;i++){
            forSort[i] = tmp[i];
        }
        delete[] tmp;
    }
    else{
        insertion(forSort,size-1);
    }
}












//ЗДЕСЬ МЭИН в котором тестируются все сортировки, замеряется время




















#include "Classes.h"
#include <iostream>
using std::cout;

int main(){
    cout<<"Sorting arrays with different sorts.\n"
        <<"\nInsertion, Bubble & Selection\n\n";
    int numberOfArrays = 10;
    int sizeOfArrays = 70000;
    int l = 1;
    int r = 7000;
    double time=0;
    cout<<"Arrays contains "<<sizeOfArrays<<" different integeres.\n"
        <<"And we have "<<numberOfArrays<<" such arrays.\n";

    SortByBubble vec(sizeOfArrays,numberOfArrays, true,l,r);
    vec.printUnsort2txt();

    cout<<"\nSorting by \"Bubble\"...\n";
    time = vec.bubbleTime();
    cout<<"Sort completed in "<<time<<"seconds.\n";

    cout<<"\nSorting by \"Selection\"...\n";
    time = vec.choiceTime();
    cout<<"Sort completed in "<<time<<"seconds.\n";

    cout<<"\nSorting by \"Insertion\"...\n";
    time = vec.insertTime();
    cout<<"Sort completed in "<<time<<"seconds.\n";

    cout<<"\nSorting by \"Shell\" using 2^i sequence (1,2,4,8,16,32...\n";
    time = vec.shellDeuceWithOutput();
    cout<<"Sort completed in "<<time<<"seconds.\n";

    cout<<"\nSorting by \"Shell\" using Hibbard sequence (every i:(2^i-1)<=N)...\n";
    time = vec.hibbardWithOutput();
    cout<<"Sort completed in "<<time<<"seconds.\n";

    cout<<"\nSorting by \"Shell\" using A102549 sequence (1,4,10,23,57,132,301,701,1750)...\n";
    time = vec.ciuraWithOutput();
    cout<<"Sort completed in "<<time<<"seconds.\n";

    cout<<"\nSorting by \"QuickSort\"...\n";
    time = vec.quickSortTime();
    cout<<"Sort completed in "<<time<<"seconds.\n";

    cout<<"\nSorting by \"QuickSort\"+\"Insertion\"...\n";
    time = vec.quickSortplusInsertionTime();
    cout<<"Sort completed in "<<time<<"seconds.\n";

    cout<<"\nSorting by \"QuickSort\"+\"Median\"...\n";
    time = vec.quickSortplusMedianTime();
    cout<<"Sort completed in "<<time<<"seconds.\n";

    cout<<"\nSorting by \"QuickSort\"+\"Med\"+\"Insertion\"...\n";
    time = vec.ultraQuickSortTime();
    cout<<"Sort completed in "<<time<<"seconds.\n";

    cout<<"\nSorting by \"HeapSort\"...\n";
    time = vec.heapSortTime();
    cout<<"Sort completed in "<<time<<"seconds.\n";

    cout<<"\nSorting by \"MergeSort\"...\n";
    time = vec.mergeSortTime();
    cout<<"Sort completed in "<<time<<"seconds.\n";

    vec.printSort2txt();
    system("pause");
    return 0;
}