TarasSortTime

#include <iostream>
#include <stdlib.h>
#include <cstdlib>
#include <ctime>
using namespace std;
const long N=100000;
double A[N], B[N], C[N], D[N], E[N];

int BubleSort(long size,double arr[])
{
    double temp;
    cout<<"Производится сортировка пузырьком"<<endl;
    int t1=clock();
    for(long i = 0; i < size - 1; ++i)
    {
        for(long j = 0; j < size - 1; ++j)
        {
            if (arr[j + 1] < arr[j])
            {
                temp = arr[j + 1];
                arr[j + 1]     = arr[j];
                arr[j] = temp;
            }
        }
    }
    int t2=clock();
    return t2-t1;
}
int selectSort(long size, double arr[])
{
    double tmp;
    cout<<"Производится сортировка выборкой"<<endl;
    int t1=clock();
    for(long i = 0; i < size; ++i) // i - номер текущего шага
    {
        int pos = i;
        tmp = arr[i];
        for(long j = i + 1; j < size; ++j) // цикл выбора наименьшего элемента
        {
            if (arr[j] < tmp)
            {
                pos = j;
                tmp = arr[j];
            }
        }
        arr[pos] = arr[i];
        arr[i] = tmp; // меняем местами наименьший с a[i]
    }
    int t2=clock();
    return t2-t1;
}
int insertSort(long size, double arr[])
{
    double tmp;
    cout<<"Производится сортировка вставкой"<<endl;
    int t1=clock();
    for (long i = 1, j; i < size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = arr[i];
        for (j = i - 1; j >= 0 && arr[j] > tmp; --j)
            arr[j + 1] = arr[j];
        arr[j + 1] = tmp;
    }
    int t2=clock();
    return t2-t1;
}
void quickSortR(long N, double* arr) {
// На входе - массив a[], a[N] - его последний элемент.

    long i = 0, j = N;      // поставить указатели на исходные места
    double temp, p;
    p = arr[ N>>1 ];      // центральный элемент
    // процедура разделения
    do {
        while ( arr[i] < p ) i++;
        while ( arr[j] > p ) j--;

        if (i <= j) {
            temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
            i++; j--;
        }
    } while ( i<=j );

    // рекурсивные вызовы, если есть, что сортировать
    if ( j > 0 ) quickSortR(j, arr);
    if ( N > i ) quickSortR(N-i,arr+i);
}
int increment(long inc[], long size)
{
    int p1, p2, p3, s;
    p1 = p2 = p3 = 1;
    s = -1;
    do
    {
        if (++s % 2)
        {
            inc[s] = 8*p1 - 6*p2 + 1;
        }
        else
        {
            inc[s] = 9*p1 - 9*p3 + 1;
            p2 *= 2;
            p3 *= 2;
        }
    p1 *= 2;
    }
    while(3*inc[s] < size);

    return s > 0 ? --s : 0;
}
int shellSort(long size, double arr[])
{
    long inc, i, j, seq[40];
    int s;
    cout<<"Производится сортировка Шелл"<<endl;
    int t1=clock();
    s = increment(seq, size); // вычисление последовательности приращений
    while (s >= 0)  // сортировка вставками с инкрементами inc[]
    {
         inc = seq[s--];
         for (i = inc; i < size; ++i)
         {
             double temp = arr[i];
             for (j = i-inc; (j >= 0) && (arr[j] > temp); j -= inc)
                arr[j + inc] = arr[j];
             arr[j] = temp;
         }
    }
    int t2=clock();
    return t2-t1;
}
int main()
{
    system("CHCP 1251>NUL");
    int Time[5];
    srand(time(NULL));
    for(int i=0; i<N;i++)
    {
        A[i] = (double)rand() / (double)RAND_MAX *100 + -50;
        B[i]=A[i];
        C[i]=A[i];
        D[i]=A[i];
        E[i]=A[i];
    }
    cout<<"Размер масива = "<<sizeof(A)/sizeof(double)<<" байт"<<endl;
    Time[0]=BubleSort(N-20000,A);
    Time[0]=BubleSort(N,A);
    cout<<"Затраченое время на сортировку массива= "<<(double)Time[0]/CLOCKS_PER_SEC<<endl;
    Time[1]=selectSort(N-20000,B);
    Time[1]=selectSort(N,B);
    cout<<"Затраченое время на сортировку массива= "<<(double)Time[1]/CLOCKS_PER_SEC<<endl;
    Time[2]=insertSort(N-20000,C);
    Time[2]=insertSort(N,C);
    cout<<"Затраченое время на сортировку массива= "<<(double)Time[2]/CLOCKS_PER_SEC<<endl;
    cout<<"Производится быстрая сортировка"<<endl;
    int t1=clock();
    quickSortR(N-20000,D);
    quickSortR(N,D);
    int t2=clock();
    Time[3]=t2-t1;
    cout<<"Затраченое время на сортировку массива= "<<(double)Time[3]/CLOCKS_PER_SEC<<endl;
    Time[4]=shellSort(N-20000,E);
    Time[4]=shellSort(N,E);
    cout<<"Затраченое время на сортировку массива= "<<(double)Time[4]/CLOCKS_PER_SEC<<endl;
    system ("pause");
    return 0;
}