void bubble(int *a,int num)
{
    int temp;
    for(int i=0;i<num;i++)
    {
        for(int n=num-1;n>i;n--)
        {
            if(a[n]<a[n-1])
            {
                temp=a[n-1];
                a[n-1]=a[n];
                a[n]=temp;
            }
        }
    }
    cout<<"sorted by bubble"<<" ";
    for(int u=0;u<num;u++)
    cout<<a[u]<<" ";
    cout<<endl;
}
int max(int *b,int i)
{
    int max=b[0],mp=0;
    for(int a=1;a<i;a++)
    {
        if(max<b[a])
        {
            max=b[a];
            mp=a;
        }
    }
    return mp;
}
void swap(int& m,int& n)
{
    int h;
    h=m;
    m=n;
    n=h;
}
void select(int *a,int num)
{
    int maxp;
    for(int i=num;i>0;i--)
    {
        maxp=max(a,i);
        swap(a[i-1],a[maxp]);
    }
    cout<<"sorted by select"<<" ";
    for(int u=0;u<num;u++)
    cout<<a[u]<<" ";
    cout<<endl;
}
void insert(int *a,int num)
{
for(int i=1;i<num;i++)
{
   int t=a[i];
   int j;
   for(j=i-1;j>=0&&t<a[j];j--)
   {
    a[j+1]=a[j];
   }
   a[j+1]=t;
}
cout<<"Sorted by insert"<<"    ";
for(int m=0;m<num;m++)
   cout<<a[m]<<" ";
cout<<endl;
}

int depart(int* a,int first,int last)
{
   div=first;
   int dp=a[first],temp;
   int left=first,right=last;
   while(left<right)
   {
    while(dp>=a[left]&&left<right)
    {
     left++;
    }
    while(dp<a[right])
    {
     right--;
    }
    if(left<right)
    {
     temp=a[left];
     a[left]=a[right];
     a[right]=temp;
    }
    temp=a[right];
    a[right]=a[first];
    a[first]=temp;
    div=right;
   }
   return div;
}
void quickSort(int* a,int first,int last)
{
   int p;
   if(first<last)
   {
    p=depart(a,first,last);
    quickSort(a,first,p-1);
    quickSort(a,p+1,last);
   }
}

void divide(int* a,int alen,int* left,int llen,int* right,int rlen)
{
   int i;
   int ll=llen;
   int rl=rlen;
   for(i=0;i<ll;i++)
    left[i]=a[i];
   for(i=0;i<rl;i++)
    right[i]=a[llen+i];
}
void merge(int* a,int alen,int* left,int llen,int* right,int rlen)
{
   int ll=llen;
   int rl=rlen;
   int i=0,q = 0;
   int leftindex=0,rightindex=0,aindex=0;
   while(leftindex<ll&&rightindex<rl)
   {
    if(left[leftindex]<right[rightindex])
    {
     a[aindex]=left[leftindex];
     leftindex++;
     aindex++;
    }else
    {
     a[aindex]=right[rightindex];
     rightindex++;
     aindex++;
    }
   }
   while(leftindex<ll)
   {
    a[aindex]=left[leftindex];
    aindex++;
    leftindex++;
   }
   while(rightindex<rl)
   {
    a[aindex]=right[rightindex];
    aindex++;
    rightindex++;
   }
}
void mergeSort(int* a,int lee)
{
int alen=lee;
   if(alen>=2)
   {
    int half=alen/2;
    int* left=new int[half];
    int llen=half;
    int* right=new int[alen-half];
    int rlen=alen-llen;
    divide(a,alen,left,llen,right,rlen);
    mergeSort(left,llen);
    mergeSort(right,rlen);
    merge(a,alen,left,llen,right,rlen);
   }
}

/*int departIndex(int *a,int min,int max)
{
int left,right;
int judge=a[min],temp;
left=min;
right=max;
while(left<right)
{
   while(a[left]<judge&&left<right)
    left++;
   while(a[right]>judge)
    right--;
   if(left<right)
   {
    temp=a[left];
    a[left]=a[right];
    a[right]=temp;
   }
}
temp=a[min];
a[min]=a[right];
a[right]=temp;
return right;
}
void quickSort(int *a,int min,int max)
{
int depart;
if(max>min)
{
   depart=departIndex(a,min,max);
   quickSort(a,min,depart-1);
   quickSort(a,depart+1,max);
}

}
int* mergeArray(int a[],int alen,int b[],int blen)
{
int *me=new int[alen+blen];
int o=0;
for(int i=0;i<alen;i++)
{
   for(int l=o;l<blen;l++)
   {
    if(a[i]<b[l])
     me[i+l]=a[i];
    else
    {
     me[i+l]=b[l];
     o++;
    }
   }
}
return me;
}
int* mergeSort(int *a,int min,int max)
{
int*array;
if(max>min)
{
int depart=max/2;
int *left=new int[depart];
int *right=new int[max-depart];
int*leftArray=mergeSort(left,0,depart);
int*rightArray=mergeSort(right,max-depart,max);
array=mergeArray(leftArray,depart,rightArray,max-depart);
}
return array;
}*/
void main()
{
    int i;
    cout<<"please enter number of your array";
    cin>>len;
    p=new int[len];
    cout<<"Please enter the element";
    for(i=0;i<len;i++)
        cin>>p[i];
    bubble(p,len);
    cout<<"Please enter the element again";
    for(i=0;i<len;i++)
        cin>>p[i];
    select(p,len);
cout<<"Please enter the element again";
for(i=0;i<len;i++)
        cin>>p[i];
insert(p,len);
cout<<"Please enter the element again";
for(i=0;i<len;i++)
        cin>>p[i];
quickSort(p,0,len-1);
cout<<"Sorted by quick"<<"    ";
for(int m=0;m<len;m++)
   cout<<p[m]<<" ";
cout<<endl;
cout<<"Please enter the element again";
for(i=0;i<len;i++)
        cin>>p[i];
mergeSort(p,len);
cout<<"Sorted by merge"<<"    ";
for(int q=0;q<len;q++)
   cout<<p[q]<<" ";
cout<<endl;

}

/*
please enter number of your array3
Please enter the element75 45 33
sorted by bubble 33 45 75
Please enter the element again3 52 2
sorted by select 2 3 52
Please enter the element again7 2 99
Sorted by insert    2 7 99
Please enter the element again21 88 11
Sorted by quick    11 21 88
Please enter the element again99 4 66
Sorted by merge    4 66 99
Press any key to continue