#include <iostream>
#include <string>
#include <stdlib.h>
#include <time.h>
#include <cstdlib>
#include <cstdio>
#include <fstream>

using namespace std;

template<class T>
 class kopiec{
       public:

       T *tab;
       int size_;
       int n;

       kopiec(){
            size_=10000000;
            n=0;
            tab = new T[size_];

            }
       ~kopiec(){}

       void push(T el){
              tab[n+1]=el;
              int tmp=n+1;
             while (tmp!=1){
                   if(tab[tmp/2] < tab[tmp]){
                                 swap(tab[tmp/2],tab[tmp]);
                                 tmp=tmp/2;
                                 }
                   else break;
                   }
             n++;
             }


            T pull(){
            cout<<tab[1]<<" ";
                 tab[1] = tab[n];
                 n--;
                 int i=1;

                 while(i*2 <= n){
                           if(tab[i]<tab[i*2] || tab[i] < tab[i*2+1]){
                                  if(tab[i*2] > tab[i*2+1] || i*2+1 > n){
                                              swap(tab[i],tab[i*2]);
                                              i=i*2;
                                              }
                                  else{
                                       swap(tab[i],tab[i*2+1]);
                                       i=i*2+1;
                                       }}
                           else break;
                                              }
                           }
              void sort(){
                   int pom = n;

                   for(int i=1; i<=n; i++){
                           swap(tab[1],tab[pom]);
                 pom--;
                 int i=1;

                 while(i*2 <= pom){
                           if(tab[i]<tab[i*2] || tab[i] < tab[i*2+1]){
                                  if(tab[i*2] > tab[i*2+1] || i*2+1 > pom){
                                              swap(tab[i],tab[i*2]);
                                              i=i*2;
                                              }
                                  else{
                                       swap(tab[i],tab[i*2+1]);
                                       i=i*2+1;
                                       }}
                           else break;
                                              }
                           }
                 if(tab[1]>tab[2]) swap(tab[1],tab[2]);
                 //   for(int j=1; j<=n; j++){
                         //   cout<<tab[j]<<" ";}
                            }

                    };



template <typename T>
struct Node{

      int id;
      T val;
      Node<T> *left;
      Node<T> *right;
      };

template <class T>
class TreeBS{
      public:

      T *tab;
      int tabsize;
      Node<T> *root;
      int sizebst;
      int iterator;

      TreeBS(){
               sizebst=0;
               root=NULL;
               tabsize=10000000;
               tab=new T[tabsize];
               iterator=0;
               }
      ~TreeBS(){

                }

      void insert(T el){

           Node<T> *node=new Node<T>();
           node->val=el;
           node->id=sizebst;
           sizebst++;
           node->left=NULL;
           node->right=NULL;


           Node<T> *it=root;

           if(it==NULL) root=node;
           else{
                         while(1){
                                  if(it->val>el){
                                                 if(it->left==NULL){
                                                                    it->left=node;
                                                                                  break;
                                                   }
                                                 else{
                                                      it=it->left;

                                                      }}


                                  else{
                                       if(it->right==NULL){
                                                           it->right=node;
                                                                                  break;
                                                                    }
                                                 else{
                                                      it=it->right;

                                                      }}}}}
           void inorder(Node<T> *wskaznik){

                if(wskaznik!=NULL){
                             inorder(wskaznik->left);

                             tab[iterator]=wskaznik->val;
                           //  cout<<tab[iterator]<<" ";
                             iterator++;

                             inorder(wskaznik->right);
                             }

                }
                                       };

int argmin(int *tab, int N){
    int min=0;
    for(int i=1; i<N; i++){
            if(tab[i]<tab[min])
            min=i;
            }
    return min;
            }

void los(int *tab, int N){
     srand(time(NULL));
     for(int i=0; i<N; i++){
             tab[i]=rand()%500;
             }}
void druk(int *tab, int N)
{
     for(int i=0; i<N; i++){
             cout<<tab[i];
             if (i<N-1){
                      cout<<", ";}
             }}

int *tabx;

void scal(int *tab, int l, int m, int r)
{
  int i = l, j = m + 1;

  for(int i = l;i<=r; i++)
    tabx[i] = tab[i];

  for(int k=l;k<=r;k++)
  if(i<=m)
    if(j <= r)
         if(tabx[j]<tabx[i])
             tab[k] = tabx[j++];
         else
             tab[k] = tabx[i++];
    else
        tab[k] = tabx[i++];
  else
      tab[k] = tabx[j++];
}

void sort_scalanie(int *tab,int l, int r)
{
  if(r<=l) return;

  int m = (r+l)/2;

  sort_scalanie(tab, l, m);
  sort_scalanie(tab, m+1, r);

  scal(tab, l, m, r);
}



void sort_wstawianie(int *tab, int N){
     int tmp;
     for(int j=1; j<N;  j++){
             if(tab[j-1]>tab[j]){
                                 tmp=tab[j];
             for (int i=j-1;i>=0;i--){
                 if(tab[i]>tmp){
                 tab[i+1]=tab[i];
                }
                 else{
                      tab[i+1]=tmp;

                      break;}}
                      if(tab[0]>tmp)
                                     tab[0]=tmp;

                      }}}


void sort_babelkowe(int *tab, int N){
     for(int i=0; i<N; i++){
             for(int j=0; j<N-1-i; j++){
                     if(tab[j]>tab[j+1]){
                          int tmp=tab[j];
                          tab[j]=tab[j+1];
                          tab[j+1]=tmp;
                          }
                     }}}
void sort_wybor(int *tab, int N){
     int min, tmp;
     for(int i=0; i<N-1; i++){
             min=argmin(tab+i,N-i);
             if(min>0){
             tmp=tab[i];
             tab[i]=tab[min+i];
             tab[min+i]=tmp;
             }
             }}

void quicksort(int *tab, int l, int r)
{
  if(r <= l) return;

  int i=l-1, j=r+1,
  X = tab[(l+r)/2];

  while(1)
  {
    while(X>tab[++i]);

    while(X<tab[--j]);

    if(i<=j)
      swap(tab[i],tab[j]);
    else
      break;
  }

  if(j>l)
  quicksort(tab, l, j);
  if(i<r)
  quicksort(tab, i, r);
}


int main()
{
    TreeBS<int> drzewo[10];
    kopiec<int> heap[10];
    int N;
    ofstream plik;
        plik.open("sortowanianowe.txt");
        //int rozmiar[]={15000,30000,45000,60000,75000,90000,105000,120000,135000,150000};
        int rozmiar2[]={50000,100000,150000,200000,250000,300000,350000,400000,450000,500000};

        clock_t start;
        double czas;
    /*    plik<<"Rozmiary tablic [x]: "<<endl<<endl;
        for (int ss=0;ss<10;ss++){
        plik<<rozmiar[ss]<<" ";}

        plik<<endl<<endl;
        for (int s=1;s<6;s++){
        switch(s){
                  case 1:
                       plik<<"SORTOWANIE BĄBELKOWE [y1]"<<endl<<endl;
                        for(int i=0;i<10;i++){
                                N=rozmiar[i];
                                int *tab=new int[N];
                                los(tab,N);

                                start = clock();
                                sort_babelkowe(tab,N);
                                czas=(clock()-start )/(double)CLOCKS_PER_SEC;
                                        cout<<endl<<"Czas: "<<czas;
                                        plik<<czas<<" ";}
                                        cout<<endl;
                                        break;

                  case 2:
                       plik<<endl<<endl<<"SORTOWANIE PRZEZ WSTAWIANIE [y2]"<<endl<<endl;
                        for(int i=0;i<10;i++){
                                N=rozmiar[i];
                                int *tab=new int[N];
                                los(tab,N);

                                start = clock();
                                sort_wstawianie(tab,N);
                                czas=(clock()-start )/(double)CLOCKS_PER_SEC;
                                        cout<<endl<<"Czas: "<<czas;
                                        plik<<czas<<" ";}
                                        cout<<endl;
                                        break;

                       case 3:
                       plik<<endl<<endl<<"SORTOWANIE PRZEZ WYBÓR [y3]"<<endl<<endl;
                        for(int i=0;i<10;i++){
                                N=rozmiar[i];
                                int *tab=new int[N];
                                los(tab,N);

                                start = clock();
                                sort_wybor(tab,N);
                                czas=(clock()-start )/(double)CLOCKS_PER_SEC;
                                        cout<<endl<<"Czas: "<<czas;
                                        plik<<czas<<" ";}
                                        cout<<endl;
                           break;

                        case 4:
                       plik<<endl<<endl<<"SORTOWANIE PRZEZ SCALANIE [y4]"<<endl<<endl;
                        for(int i=0;i<10;i++){
                                N=rozmiar[i];
                                int *tab=new int[N];
                                tabx = new int[N];
                                los(tab,N);

                                start = clock();
                                sort_scalanie(tab,0,N-1);
                                czas=(clock()-start )/(double)CLOCKS_PER_SEC;
                                        cout<<endl<<"Czas: "<<czas;
                                        plik<<czas<<" ";}
                                        cout<<endl;

                                break;

                        case 5:
                       plik<<endl<<endl<<"QUICK SORT [y5]"<<endl<<endl;
                        for(int i=0;i<10;i++){
                                N=rozmiar[i];
                                int *tab=new int[N];
                                los(tab,N);

                                start = clock();
                                quicksort(tab, 0, N-1);
                                czas=(clock()-start )/(double)CLOCKS_PER_SEC;
                                        cout<<endl<<"Czas: "<<czas;
                                        plik<<czas<<" ";}
                                        cout<<endl<<endl;
                           break;

                            }

} */
    //  cout<<sizeof(int);
                    plik<<endl<<endl<<"Rozmiary tablic [x2]: "<<endl<<endl;
                    for (int ssss=0;ssss<10;ssss++){
           plik<<rozmiar2[ssss]<<" ";}
                for(int sss=1; sss<5; sss++){
                    switch(sss){

                        case 1:
                       plik<<endl<<endl<<"SORTOWANIE PRZEZ SCALANIE [y6]"<<endl<<endl;
                        for(int i=0;i<10;i++){
                                N=rozmiar2[i];
                                int *tab=new int[N];
                                tabx = new int[N];
                                start = clock();
                                los(tab,N);

                                sort_scalanie(tab,0,N-1);
                                czas=(clock()-start )/(double)CLOCKS_PER_SEC;
                                        cout<<endl<<"Czas: "<<czas;
                                        plik<<czas<<" ";}
                                        cout<<endl;

                                break;

                        case 2:
                       plik<<endl<<endl<<"QUICK SORT [y7]"<<endl<<endl;
                        for(int i=0;i<10;i++){
                                N=rozmiar2[i];
                                int *tab=new int[N];

                                start = clock();
                                los(tab,N);


                                quicksort(tab, 0, N-1);
                                czas=(clock()-start )/(double)CLOCKS_PER_SEC;
                                        cout<<endl<<"Czas: "<<czas;
                                        plik<<czas<<" ";}
                                        cout<<endl;
                           break;

                    case 3:
                       plik<<endl<<endl<<"HEAPSORT [y7]"<<endl<<endl;
                        for(int i=0;i<10;i++){
                                N=rozmiar2[i];
                                start = clock();
                                for(int licz=0; licz<N; licz++){
                                heap[i].push(rand()%500);
                                }


                                heap[i].sort();
                                czas=(clock()-start )/(double)CLOCKS_PER_SEC;
                                        cout<<endl<<"Czas: "<<czas;
                                        plik<<czas<<" ";}
                                        cout<<endl;
                           break;

                    case 4:
                       plik<<endl<<endl<<"BST sort [y7]"<<endl<<endl;
                        for(int i=0;i<10;i++){
                                N=rozmiar2[i];

                                start = clock();
                                for(int liczn=0; liczn<N; liczn++){
                                drzewo[i].insert(rand()%5000000);
                                }


                                drzewo[i].inorder(drzewo[i].root);
                                czas=(clock()-start )/(double)CLOCKS_PER_SEC;
                                        cout<<endl<<"Czas: "<<czas;
                                        plik<<czas<<" ";}
                                        cout<<endl;
                           break;
                    }
                }
plik.close();
cout<<endl;
system("pause");
return (0);
}