/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <cmath>

using namespace std;

int count_sw = 0;


void q_sort(int *tab, int left, int right)
{

    int i = left - 1, j = right + 1,
    pivot = tab[left];
    while(1)
    {

        while(pivot>tab[++i]);
        while(pivot<tab[--j]);
        if( i <= j)
        {
            swap(tab[i],tab[j]);
            count_sw++;

        }
        else
            break;
    }
    if(j > left)
    q_sort(tab, left, j);
    if(i < right)
    q_sort(tab, i, right);
}



int main()
{

    srand( time( NULL ) );
    int size =10;
    int *tab, n[size];
    clock_t start, stop;


    double times [size];
    for(int c = 0 ; c < size; c++ )
    {
        n [c] = (c+1) * 1000;
        count_sw = 0;
        tab = new int [n[c]];
        for(int i=0;i<n[c];i++)
            tab[i] = rand()%n[c];//

        start = clock();
        q_sort(tab,0, n[c]-1);
        stop = clock();
        cout <<"size "<<n[c]<<"   changes-"<<count_sw<<'\n';
        for(int i=0;i<n[c];i++)
            //cout<<tab[i]<<' ';//rand()%n[c];
        //cout<<'\n';
        count_sw =0;
        times[c] = (double)(stop-start) / CLOCKS_PER_SEC;
        delete[] tab;
    }

    for(int c = 0 ; c < size; c++ )
    {
        cout<< /*n[c]<< "\n"<<*/times[c]<<'\n';
    }


    return 0;
}