#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define n 1000000

void makeArray(int *a,int *b,int *c,int *a1,int *b1,int *c1);
void quickSort(int *Array,int Limit);
void qSort(int *Array,int l,int r,int Limit);
void mergeSort(int *Array , int l ,int r);
void copy(int *a,int *b);
void revers(int *a,int *b);
void merge(int *Array , int l,int m,int r);

int main()
{
 int i;
 int a[n]={NULL,},b[n]={NULL,},c[n]={NULL,},a1[n]={NULL,},b1[n]={NULL,},c1[n]={NULL,};
 makeArray(a,b,c,a1,b1,c1);
 clock_t start,end,time;
 start=clock();
 quickSort(a,0);
 end=clock();
 time = end - start;
 printf("무작위리스트 퀵정렬 소요시간: %f\n",(double)time/CLOCKS_PER_SEC);
 start=clock();
 quickSort(b,0);
 end=clock();
 time = end - start;
 printf("정순리스트 퀵정렬 소요시간: %f\n",(double)time/CLOCKS_PER_SEC);
 start=clock();
 quickSort(c,0);
 end=clock();
 time = end - start;
 printf("역순리스트 퀵정렬 소요시간: %f\n\n\n",(double)time/CLOCKS_PER_SEC);
 start=clock();
 mergeSort(a1, 0 , n-1);
 end=clock();
 time = end - start;
 printf("무작위리스트 합병정렬 소요시간: %f\n",(double)time/CLOCKS_PER_SEC);
 start=clock();
 mergeSort(b1, 0 , n-1);
 end=clock();
 time = end - start;
 printf("정순리스트 합병정렬 소요시간: %f\n",(double)time/CLOCKS_PER_SEC);
 start=clock();
 mergeSort(c1, 0 , n-1);
 end=clock();
 time = end - start;
 printf("역순리스트 합병정렬 소요시간: %f\n",(double)time/CLOCKS_PER_SEC);
 
 
 
 
 return 0;
}

void makeArray(int *a,int *b,int *c,int *a1,int *b1,int *c1)
{
 int i;
 srand(time(NULL));
 for(i=0; i < n; i++)
 {
  a[i] = rand()%100+1;
  b[i] = a[i];
 }
 quickSort(b,50);
 revers(b,c);
 copy(a,a1);
 copy(b,b1);
 copy(c,c1);
 return;
}

void quickSort(int *Array,int Limit)
{
 qSort(Array,0,n-1,Limit);
 return;
}

void qSort(int *Array,int l,int r,int Limit)
{
 int p = Array[r];
 int i=l , j=r;
 while(i<j)
 {
  
  while((i<j) && (Array[i]<=p))
  {
   i++;
  }
  
  if(i != j)
  {
   Array[j] = Array[i];
   j--;
  }
  while((i<j) && (Array[j]>=p))
  {
   j--;
  }
  if(i != j)
  {
   Array[i] = Array[j];
  }
 }
 Array[i]=p;
 p=i;
 if(r-l < Limit)
 {
  return;
 }
 if (l < p)
 {
        qSort(Array, l, p - 1,Limit);
 }
    if (r > p)
 {
        qSort(Array, p+1, r,Limit);
 }
 
 return;
}

void copy(int *a,int *b)
{
 int i;
 for(i=0; i<n; i++)
 {
  b[i]=a[i];
 }
 return;
}
void revers(int *a,int *b)
{
 int i;
 for(i=0; i<n; i++)
 {
  b[n-i-1]=a[i];
 }
 return;
}

void mergeSort(int *Array , int l ,int r)
{
 if(l<r)
 {
  int m = (l+r)/2;
  mergeSort(Array , l ,m);
  mergeSort(Array,m+1,r);
  merge(Array,l,m,r);
 }
 return;
}

void merge(int *Array , int l,int m,int r)
{
 int B[n] = {NULL,};
 int i=l,k=l;
 int j=m+1;
 while(i <= m && j<= r)
 {
  if(Array[i] <= Array[j])
  {
   B[k++] = Array[i++];
  }
  else
  {
   B[k++] = Array[j++];
  }
 }
 while(i<=m)
 {
  B[k++] = Array[i++];
 }
 while(j<=r)
 {
  B[k++]=Array[j++];
 }
 for(k=l; k <= r; k++)
 {
  Array[k] = B[k];
 }
 return;
}

//제 과제인데 이게 한 1~2만개에선 잘나오는데 10만개 넘어가면 그냥 아무키나 누르라고 밖에 안뜨더라구요....다른컴퓨터에선 어떨까 해서..이거좀 실행해주세요