#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/*
#include "Profiler.h"

#define MAX_SIZE 10000
#define STEP_SIZE 10
#define NUM_TEST 10

Profiler p("Traversal");
enum Traversal{Post,Pre,In};

typedef struct Node{
    int key;
    struct Node *right;
    struct Node *left;
    struct Node *parent;
};
int op;
void PrettyPrint(Node *node,int space){

    if(NULL!=node){

        for(int i=0;i<space;i++)
            printf("   ");

        printf("%d\n",node->key);
        PrettyPrint(node->left,space+1);
        PrettyPrint(node->right,space+1);
    }

}
void IterativeTraversal(Node **root,Traversal traversal){
  int direction=1;
  Node *node=(*root);
  do{
      if(direction==1){

          if(traversal==Pre){
              op+=1;
              printf("%d ",node->key);
          }

          if(NULL!=node->left)
              node=node->left;
          else direction=2;
      }
      if(direction==2){

          if(traversal==In){
              op+=1;
              printf("%d ",node->key);
          }

          if(NULL!=node->right) {
              node = node->right;
              direction=1;
          }
          else direction=3;
      }
      if(direction==3){

          if(traversal==Post){
              op+=1;
             printf("%d ",node->key);
          }

          if(NULL!=node->parent){
              if(node==node->parent->left)
                  direction=2;

              node=node->parent;
          }
      }
  }
  while((*root)!=node || direction!=3);

    if(traversal==Post){
        op+=1;
        printf("%d ",node->key);
    }

}
void PreorderTraversal(Node *node){
    if(NULL==node)
        return;

    op+=1;
    printf("%d ",node->key);
    PreorderTraversal(node->left);
    PreorderTraversal(node->right);
}
void PostorderTraversal(Node *node){
    if(NULL==node)
        return;

    PostorderTraversal(node->left);
    PostorderTraversal(node->right);
    printf("%d ",node->key);
    op+=1;
}
void InorderTraversal(Node *node){
    if(NULL==node)
        return;

    InorderTraversal(node->left);
    op+=1;
    printf("%d ",node->key);
    InorderTraversal(node->right);
}
void InsertInTree(Node **root, int key){

    if(NULL==(*root)){
        Node *temp = (Node *) malloc(sizeof(Node));
        temp->parent=NULL;
        temp->right=NULL;
        temp->left=NULL;
        temp->key=key;
        (*root)=temp;
        return;
    }

    Node *curr_node=(*root);
    int ok=false;
    while(!ok){
        if(key>curr_node->key) {

            if (NULL == curr_node->right) {
                Node *temp = (Node *) malloc(sizeof(Node));
                temp->parent=curr_node;
                temp->right=NULL;
                temp->left=NULL;
                temp->key=key;
                curr_node->right=temp;
                curr_node=curr_node->right;
                ok= true;
            }
            else curr_node=curr_node->right;
        }
        else if(key<curr_node->key){

            if (NULL == curr_node->left) {
                Node *temp = (Node *) malloc(sizeof(Node));
                temp->parent=curr_node;
                temp->right=NULL;
                temp->left=NULL;
                temp->key=key;
                curr_node->left=temp;
                curr_node=curr_node->left;
                ok= true;
            }
            else curr_node=curr_node->left;
        }
    }
}
Node *GetMinimum(Node *root){
    while(root->left!=NULL)
        root=root->left;

    return root;
}
Node *DeleteInTree(Node *node,int key){

    if(node==NULL)
        return node;

    if(key>node->key){
        node->right= DeleteInTree(node->right,key);
    }
    else if(key<node->key){
        node->left= DeleteInTree(node->left,key);
    }
    else{

        if(NULL==node->left && NULL==node->right){
            free(node);
            node=NULL;
        }
        else if(NULL==node->left){
            Node *temp=node;
            node=node->right;
            free(temp);
            temp=NULL;
        }
        else if(NULL==node->right){
            Node *temp=node;
            node=node->left;
            free(temp);
            temp=NULL;
        }
        else{
            Node *temp= GetMinimum(node->right);
            node->key=temp->key;
            node->right= DeleteInTree(node->right,temp->key);
        }
    }
    return node;

}
void Analysis(){

    int arr[MAX_SIZE];
    Node *root=NULL;
    for(int n=STEP_SIZE;n<=MAX_SIZE;n+=STEP_SIZE){
        Operation IterativePre=p.createOperation("Iterative Preorder",n);
        Operation IterativePost=p.createOperation("Iterative Postorder",n);
        Operation IterativeIn=p.createOperation("Iterative Inorder",n);
        Operation RecursivePre=p.createOperation("Recursive Preorder",n);
        Operation RecursivePost=p.createOperation("Recursive Postorder",n);
        Operation RecursiveIn=p.createOperation("Recursive Inorder",n);
        for(int test=0;test<NUM_TEST;test++){
            FillRandomArray(arr,n,10,50000,true,UNSORTED);

            for(int i=0;i<n;i++)
                InsertInTree(&root,arr[i]);

            op=0;
            IterativeTraversal(&root,Pre);
            IterativePre.count(op);

            op=0;
            IterativeTraversal(&root,Post);
            IterativePost.count(op);

            op=0;
            IterativeTraversal(&root,In);
            IterativeIn.count(op);

            op=0;
            PreorderTraversal(root);
            RecursivePre.count(op);

            op=0;
            PostorderTraversal(root);
            RecursivePost.count(op);

            op=0;
            InorderTraversal(root);
            RecursiveIn.count(op);

            for(int i=0;i<n;i++)
                root= DeleteInTree(root,arr[i]);
        }
    }

    p.divideValues("Iterative Preorder",NUM_TEST);
    p.divideValues("Iterative Postorder",NUM_TEST);
    p.divideValues("Iterative Inorder",NUM_TEST);
    p.divideValues("Recursive Preorder",NUM_TEST);
    p.divideValues("Recursive Postorder",NUM_TEST);
    p.divideValues("Recursive Inorder",NUM_TEST);
    p.showReport();

}
void Demo(){

    int arr[13];
    FillRandomArray(arr,13,10,45,true,UNSORTED);
    Node *root=NULL;
    for(int i=0;i<13;i++)
        InsertInTree(&root,arr[i]);

    printf("\n---Pretty Print---\n");
    PrettyPrint(root,0);

    printf("\n--Recursive Preorder---\n");
    PreorderTraversal(root);

    printf("\n--Recursive Postorder---\n");
    PostorderTraversal(root);

    printf("\n--Recursive Inorder---\n");
    InorderTraversal(root);

    printf("\n--Iterative Preorder---\n");
    IterativeTraversal(&root,Pre);

    printf("\n--Iterative Postorder---\n");
    IterativeTraversal(&root,Post);

    printf("\n--Iterative Inorder---\n");
    IterativeTraversal(&root,In);



}*/
void InsertionSort(int *v,int low,int high){
    int ind;
    int aux,elem;
    for(int i=low;i<high;i++){
        ind=i;
        elem=v[ind+1];
        while(ind>=0 && v[ind]>elem){
            v[ind+1]=v[ind];
            ind--;
        }

        if(ind!=i) {
            v[ind + 1] = elem;
        }
    }
}
int Partition(int *arr,int low,int high){
    int aux;
    int pivot=low;
  while(low<=high){

      while(arr[low]<arr[pivot])
          low++;
      while(arr[high]>arr[pivot])
          high--;

      if(low<high){
          aux=arr[low];
          arr[low]=arr[high];
          arr[high]=aux;
          low++;
          high--;
      }
      else break;
  }
  aux=arr[high];
  arr[high]=arr[pivot];
  arr[pivot]=aux;
  return high;
}
void QuickSort(int *arr,int low,int high){
  if(low<high){

          int p = Partition(arr, low, high);
          QuickSort(arr, low, p - 1);
          QuickSort(arr, p + 1, high);
  }
}
void HybridQuickSort(int *arr,int low,int high){
    if(low<high){
        if(high-low<30)
            InsertionSort(arr,low,high);
        else {
            srand(time(NULL));
            int rand_index = rand() % (high - low) + low;
            int aux = arr[low];
            arr[low] = arr[rand_index];
            arr[rand_index] = aux;
            int p = Partition(arr, low, high);
            QuickSort(arr, low, p - 1);
            QuickSort(arr, p + 1, high);
        }
    }
}
void DemoQuickSort(){

    int N=23;
    int arr[N];
 //   FillRandomArray(arr,N,10,50,false,UNSORTED);
    for(int i=0;i<23;i++)
        printf("%d ",arr[i]);
    printf("\n");
    QuickSort(arr,0,N-1);
    for(int i=0;i<23;i++)
        printf("%d ",arr[i]);
}
void DemoHybridQuickSort(){
    int N=23;
    int arr[N];
   // FillRandomArray(arr,N,10,50,false,UNSORTED);
    for(int i=0;i<23;i++)
        printf("%d ",arr[i]);
    printf("\n");
    HybridQuickSort(arr,0,N-1);
    for(int i=0;i<23;i++)
        printf("%d ",arr[i]);
}
int main() {

    //Analysis();
   // Demo();
//    freopen("algsort.in","r",stdin);
//   freopen("algsort.out","w",stdout);
//
//    int N;
//    scanf("%d",&N);
//    int *arr=(int *) malloc(sizeof(int)*N);
//    for(int i=0;i<N;i++)
//        scanf("%d",&arr[i]);
//
//    HybridQuickSort(arr,0,N-1);
//    for(int i=0;i<N;i++)
//        printf("%d ",arr[i]);

   //DemoQuickSort();
   DemoHybridQuickSort();

   return 0;
}