#include <iostream>
#include <ctime>
#include <algorithm>


const int size = 100000;
int v[size];

void init_array(int v[])
{
	const int x=1, y=size;
	srand(static_cast<unsigned int>(time(0)));
	for (int i=0;i<size;++i)
		v[i]=x+static_cast<int>((rand()+1.0)/(RAND_MAX+1.0)*(y-x));

}

class PQ 
{
     private:
          int *a;
          int N;
     public:
          PQ(int max)
               { a = new int[max]; N = 0; }
          ~PQ()
               { delete a; }
          void insert(int v)
               { a[++N] = v; upheap(N); }
          void upheap(int k);
          void downheap(int k);
          int remove();
          int replace(int v);
};

void PQ::upheap(int k)
{
     int v;
     v = a[k]; a[0]=0;
     while (a[k/2] <= v)                        
          { a[k] = a[k/2]; k = k/2; }
     a[k] = v;
}

void PQ::downheap(int k) {
     int j; int v;
     v = a[k];
     while (k <= N/2) {
          j = k+k;
          if (j<N && a[j]<a[j+1]) j++;
          if (v >= a[j]) break;
          a[k] = a[j]; k = j;
     }
     a[k]=v;
}

int PQ::remove() 
{
     int v = a[1];
     a[1]= a[N--];
     downheap(1);
     return v;
}

int PQ::replace(int v) 
{
     a[0]=v;
     downheap(0);
     return a[0];
}


void heapsort(int a[], int N) 
{
     int i; PQ heap(N);
     for (i=1; i <= N; i++) heap.insert(a[i]);
     for (i=N; i >= 1; i--) a[i]=heap.remove();
}

void qs(int v[], int high, int low)
{
	
	long i=low;
	long j=high;
	int temp;
	int p=v[(low+high)/2];
	do 
	{
		while (v[i]<p) i++;
		while (v[j]>p) j--;
		if (i<=j){
					temp=v[i];
					v[i]=v[j];
					v[j]=temp;
					i++;
					j--;
		         }
	}
	while(i<=j);
    if (j>low) qs(v,j,low);
	if (high>i) qs(v,high,i);
}

void sort_shell( int v[ ], const int size )
{
        int i, j, tmp, step=size/2;
 
        while (step > 0) 
		{
                for (i=0; i<(size-step); i++) 
				{
                        j = i;
                        while ( (j >= 0) && (v[j] > v[j+step]) ) 
						{
                                tmp = v[j];
                                v[j] = v[j+step];
                                v[j+step] = tmp;
                                j--;
                        }                 
                }
                step /= 2;
        } 
}



void viborka(int v[], const int size)
{
	int min;
	int a;
	for (int i=0;i<size;++i)
	{
		min=i;
		for (int j=i;j<size;++j)
			if (v[j]<v[min]) min=j;
		a=v[i];
		v[i]=v[min];
		v[min]=a;
	}
}

using namespace std;
int main()
{	
	clock_t start,finish;
	double duration;
	init_array(v);
	int v1[size];
	int v2[size];
	int v3[size];
	int v4[size];
	copy(&v[0],&v[size],&v1[0]);
	copy(&v[0],&v[size],&v2[0]);
	copy(&v[0],&v[size],&v3[0]);
	copy(&v[0],&v[size],&v4[0]);
	start=clock();
	sort(&v[0],&v[size]);
	finish=clock();
	duration = static_cast<double>(finish-start)/CLOCKS_PER_SEC;
	cout<<duration<<endl;
	start=clock();
	qs (v1, size, 0);
	finish=clock();
	duration = static_cast<double>(finish-start)/CLOCKS_PER_SEC;
	cout<<duration<<endl;
	start=clock();
	heapsort (v2, size);
	finish=clock();
	duration = static_cast<double>(finish-start)/CLOCKS_PER_SEC;
	cout<<duration<<endl;
	start=clock();
	sort_shell (v3, size);
	finish=clock();
	duration = static_cast<double>(finish-start)/CLOCKS_PER_SEC;
	cout<<duration<<endl;
	start=clock();
	viborka (v4, size);
	finish=clock();
	duration = static_cast<double>(finish-start)/CLOCKS_PER_SEC;
	cout<<duration<<endl;	
}