#include <iostream>
#include <cmath>
#include <stdlib.h>
#include <ctime>

using namespace std;

void wyswietlanie(int n, int t[])
  {
    for(int i=0; i<n; i++)
    {
        cout<<t[i]<<" ";
    }

    cout<<endl;
  }
int maksimum(int n, int t[])
{
    int max=0;
    for(int i=0; i<n; i++)
    {
        if(t[i]>max)
        {
            max=t[i];
        }
    }
    return max;
}
int Max_element_indeks(int n, int t[])
   {
     int max = 0;
     for (int i = 1; i < n; i++)
       if (t[i] > t[max])
         max = i;
     return max;
   }

void Selection_sort(int n, int t[])
  {
    for (int i = n; i >= 2; i--)
    {
      int max = Max_element_indeks(i, t);
      if (max != i - 1)
        swap(t[i - 1], t[max]);
    }

    cout<<"Select_sort: ";
  }

void Insert_sort(int n, int t[])
{
    for(int i=1; i<n; i++)
    {
        int j=i;
        int temp=t[j];

        while((j>0) && t[j-1]>temp)
        {
            t[j]=t[j-1];
            j--;

        }
        t[j]=temp;
    }

    cout<<"Insert_sort: ";

}

void bubblesort(int n, int t[])
{

    for(int i=0; i<n-1;i++)
    {
        for(int j=0; j<n-1-i; j++)
        {
            if(t[j+1] < t[j])
                {
                swap(t[j+1], t[j]);

                    }
        }
    }

    cout<<"bubble_sort: ";
}

int quick_sort(int t[], int lo, int hi)
{
    int i=lo;
    int j=hi;

    int x=t[(lo+hi)/2];
    do
    {
        while(t[i]<x) i++;
        while(t[j]>x) j--;
        if(i<=j)
        {
            swap(t[i], t[j]);
            i++;
            j--;
        }

    }while(i<=j);

    if(lo<j) quick_sort(t, lo, j);
    if(hi>i) quick_sort(t, i, hi);
}

void count_sort(int T[], int n, int maksimum){
int k=maksimum;
int *Tp;
Tp=new int [n];

int *TPom;
TPom=new int[k+1];

int i;

  for(i = 0 ; i < k+1 ; ++i)
    TPom[i] = 0;

  for(i = 0 ; i < n ; ++i)
    ++TPom[T[i]];

  for(i = 1 ; i < k+1 ; ++i)
    TPom[i] += TPom[i-1];

  for(i = n-1 ; i >= 0 ; --i)
    Tp[--TPom[T[i]]] = T[i]  ;


  for(i=0; i<n; i++)
  {
      T[i]=Tp[i];
  }

delete[] Tp;
delete[] TPom;
}

void merge(int a[], const int low, const int mid, const int high)
{

	int * b = new int[high+1-low];
	int h,i,j,k;
	h=low;
	i=0;
	j=mid+1;

	while((h<=mid)&&(j<=high))
	{
		if(a[h]<=a[j])
		{
			b[i]=a[h];
			h++;
		}
		else
		{
			b[i]=a[j];
			j++;
		}
		i++;
	}

	if(h>mid)
	{
		for(k=j;k<=high;k++)
		{
			b[i]=a[k];
			i++;
		}
	}
	else
	{
		for(k=h;k<=mid;k++)
		{
			b[i]=a[k];
			i++;
		}
	}

	for(k=0;k<=high-low;k++)
	{
		a[k+low]=b[k];
	}
	delete[] b;
}

void merge_sort(int a[], const int low, const int high)
{
	int mid;
	if(low<high)
	{
		mid=(low+high)/2;
		merge_sort(a, low,mid);
		merge_sort(a, mid+1,high);
		merge(a, low,mid,high);
	}
}

int rosnaco(int n, int t[])
  {
      for(int i=0; i<n; i++)
      {
          t[i]=i;
      }
  }

int malejaco(int n, int t[])
  {
      for(int i=n; i>0; i--)
      {
          t[n-i]=i;
      }
  }

void losowo(int n, int t[])
{
    srand((unsigned) time(NULL));

    for(int i=0; i<n; i++)
    {
        int liczba = rand() % 100 + 1;
        t[i]= liczba;
    }
}


int main()
{
    for(int i=1; i<8; i++)
    {
        int stopien=pow(10,i);
        int *tab = new int [stopien];
        clock_t start, stop;
        double czas;
    if(i==1)
    {

        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        Selection_sort(stopien, tab);
        stop = clock();
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo: "<<endl;
        losowo(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        Selection_sort(stopien, tab);
        stop = clock();
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        wyswietlanie(stopien, tab);
        start=clock();
        Selection_sort(stopien, tab);
        stop =clock();
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<endl;
        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        Insert_sort(stopien, tab);
        stop = clock();
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo"<<endl;
        losowo(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        Insert_sort(stopien, tab);
        stop = clock();
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        Insert_sort(stopien, tab);
        stop = clock();
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;


        cout<<endl;
        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        bubblesort(stopien, tab);
        stop = clock();
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo"<<endl;
        losowo(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        bubblesort(stopien, tab);
        stop = clock();
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        bubblesort(stopien, tab);
        stop = clock();
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<endl;
        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        quick_sort(tab, 0, stopien);
        stop = clock();
        cout<<"quick_sort: "<<endl;
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo"<<endl;
        losowo(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        quick_sort(tab, 0, stopien);
        stop = clock();
        cout<<"quick_sort: "<<endl;
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        quick_sort(tab, 0, stopien);
        stop = clock();
        cout<<"quick_sort: "<<endl;
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<endl;
        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        count_sort(tab, stopien, maksimum(stopien, tab));
        stop = clock();
        cout<<"count_sort: "<<endl;
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo"<<endl;
        losowo(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        count_sort(tab, stopien, maksimum(stopien, tab));
        stop = clock();
        cout<<"count_sort: "<<endl;
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        count_sort(tab, stopien, maksimum(stopien, tab));
        stop = clock();
        cout<<"count_sort: "<<endl;
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<endl;
        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        merge_sort(tab,0, stopien);
        stop = clock();
        cout<<"merge_sort: "<<endl;
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo"<<endl;
        losowo(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        merge_sort(tab,0, stopien);
        stop = clock();
        cout<<"merge_sort: "<<endl;
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        wyswietlanie(stopien, tab);
        start = clock();
        merge_sort(tab,0, stopien);
        stop = clock();
        cout<<"merge_sort: "<<endl;
        wyswietlanie(stopien, tab);
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;
      }

      else

      {

        if(i<5)
        {
        cout<<endl;
        cout<<"10^"<<i<<endl;
        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        start = clock();
        Selection_sort(stopien, tab);
        stop = clock();
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo"<<endl;
        losowo(stopien, tab);
        start = clock();
        Selection_sort(stopien, tab);
        stop = clock();
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        start=clock();
        Selection_sort(stopien, tab);
        stop =clock();
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<endl;
        cout<<"10^"<<i<<endl;
        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        start = clock();
        Insert_sort(stopien, tab);
        stop = clock();
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo"<<endl;
        losowo(stopien, tab);
        start = clock();
        Insert_sort(stopien, tab);
        stop = clock();
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        start = clock();
        Insert_sort(stopien, tab);
        stop = clock();
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;


        cout<<endl;
        cout<<"10^"<<i<<endl;
        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        start = clock();
        bubblesort(stopien, tab);
        stop = clock();
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo"<<endl;
        losowo(stopien, tab);
        start = clock();
        bubblesort(stopien, tab);
        stop = clock();
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        start = clock();
        bubblesort(stopien, tab);
        stop = clock();
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<endl;
        cout<<"10^"<<i<<endl;
        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        start = clock();
        quick_sort(tab, 0, stopien);
        stop = clock();
        cout<<"quick_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo"<<endl;
        losowo(stopien, tab);
        start = clock();
        quick_sort(tab, 0, stopien);
        stop = clock();
        cout<<"quick_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        start = clock();
        quick_sort(tab, 0, stopien);
        stop = clock();
        cout<<"quick_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<endl;
        cout<<"10^"<<i<<endl;
        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        start = clock();
        count_sort(tab, stopien, maksimum(stopien, tab));
        stop = clock();
        cout<<"count_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo"<<endl;
        losowo(stopien, tab);
        start = clock();
        count_sort(tab, stopien, maksimum(stopien, tab));
        stop = clock();
        cout<<"count_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        start = clock();
        count_sort(tab, stopien, maksimum(stopien, tab));
        stop = clock();
        cout<<"count_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<endl;
        cout<<"10^"<<i<<endl;
        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        start = clock();
        merge_sort(tab,0, stopien);
        stop = clock();
        cout<<"merge_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo"<<endl;
        losowo(stopien, tab);
        start = clock();
        merge_sort(tab,0, stopien);
        stop = clock();
        cout<<"merge_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        start = clock();
        merge_sort(tab, 0, stopien);
        stop = clock();
        cout<<"merge_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        }
        else
        {
        cout<<endl;
        cout<<"10^"<<i<<endl;
        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        start = clock();
        quick_sort(tab, 0, stopien);
        stop = clock();
        cout<<"quick_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo"<<endl;
        losowo(stopien, tab);
        start = clock();
        quick_sort(tab, 0, stopien);
        stop = clock();
        cout<<"quick_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        start = clock();
        quick_sort(tab, 0, stopien);
        stop = clock();
        cout<<"quick_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<endl;
        cout<<"10^"<<i<<endl;
        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        start = clock();
        count_sort(tab, stopien, maksimum(stopien, tab));
        stop = clock();
        cout<<"count_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo"<<endl;
        losowo(stopien, tab);
        start = clock();
        count_sort(tab, stopien, maksimum(stopien, tab));
        stop = clock();
        cout<<"count_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        start = clock();
        count_sort(tab, stopien, maksimum(stopien, tab));
        stop = clock();
        cout<<"count_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<endl;
        cout<<"10^"<<i<<endl;
        cout<<"rosnaco"<<endl;
        rosnaco(stopien, tab);
        start = clock();
        merge_sort(tab,0, stopien);
        stop = clock();
        cout<<"merge_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"losowo"<<endl;
        losowo(stopien, tab);
        start = clock();
        merge_sort(tab,0, stopien);
        stop = clock();
        cout<<"merge_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        cout<<"malejaco"<<endl;
        malejaco(stopien, tab);
        start = clock();
        merge_sort(tab, 0, stopien);
        stop = clock();
        cout<<"merge_sort: "<<endl;
        czas = (stop - start);
        cout<<"czas w tikach procesora: "<<czas<<endl;

        }
      }
    delete[] tab;
    }
    return 0;
}