// zheban.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "time.h"
#include "stdlib.h"
#define NUM 10000

void printArray(int arr[],int n);//聲明打印函數
void RandomArray(int arr[],int n);//聲明隨機生成函數

void bubble(int arr[],int n);//聲明冒泡函數
void select(int arr[],int n);//聲明選擇函數
void insert(int arr[],int n);//聲明折半插入函數
void quick(int arr[],int startPos, int endPos) ;//聲明快排函數
void MSort(int *,int *,int,int);//聲明歸并函數
void Merge(int SR[],int TR[], int i,int m, int n);

int main(int argc, char* argv[])//定義主函數
{

	int arr[NUM];
	int currenttime;
	int d;
	
	while(1)
	{
		printf("please press any key to get Random array:\n");
		getchar();
		RandomArray(arr,NUM);//調用隨機函數
        printArray(arr,NUM);//調用打印函數
		printf("==========================================================================\n");
		printf("1----bubble\n\n2----select\n\n3----merge\n\n4----quick\n\n5----insert\n\n0----exit\n\n\nPress the number to sort the array!\n\n");
		scanf("%d",&d);
		currenttime=clock();//獲取當前時間
		switch(d)
		{
		case 1:
			bubble(arr,NUM);
			break;
		case 2:
			select(arr,NUM);
			break;
		case 3:
			MSort(arr,arr,0,NUM-1);
			break;
		case 4:
			quick(arr,0,NUM);
			break;
		case 5:
			insert(arr,NUM);
			break;
		}	
		currenttime=clock()-currenttime;//計算運行時間
		if(d==0)
			break;	
		printArray(arr,NUM);
		printf("\n\n\nThe use time of this kink of sort is:%d毫秒\n\n\n",currenttime);
		printf("Please input anykey to go on!");
		getchar();
		getchar();		
		printf("\n\n\n\n\n");
	}
	return 0;
}

void RandomArray(int arr[],int n)//定義產生隨機數函數
{
	srand((unsigned)time(NULL));
	for(int i=0;i<n;i++)
	{		 
		arr[i]=rand();
	}
}

void printArray(int arr[],int n)//定義打印函數
{

	for(int i=0;i<n;i++)
	{
		printf("%7d",arr[i]);
		if((i+1)%10==0)
		{
			printf("\n");
		}
	}
}

void bubble(int arr[],int n)//定義冒泡排序
{
	int i,j,t;
	for(j=0;j<n-1;j++)
		for(i=0;i<n-j-1;i++) 
			if(arr[i]>arr[i+1]) 
			{t=arr[i];arr[i]=arr[i+1];arr[i+1]=t;}
}

void select(int a[],int n)//定義選擇排序
{
	int k,j;
	for(int i=0;i<n-1;i++)
	{
		k=i;
		for (j=i+1;j<n;j++)
			if(a[j]<a[k])
			{
				int temp=a[k];
				a[k]=a[j];
				a[j]=temp;
			}
	}
}



void insert(int arr[],int n)//定義折半排序 
{
	int temp;
	int low,high,mid;
	for (int i=1; i<n; ++i )
	{
		temp = arr[i];
		low = 0; high = i-1;
		while (low<=high) 
		{
			mid = (low+high)/2;
			if (temp < arr[mid])
				high = mid-1;
			else low = mid+1;
		}
		for (int j=i-1; j>=high+1; --j )
			arr[j+1] = arr[j];
		arr[high+1] = temp;
	}
}

void quick(int arr[],int startPos, int endPos) //定義快排排序
{
	int i,j;
	int temp; 
	temp=arr[startPos]; 
	i=startPos; 
	j=endPos; 
	while(i<j) 
	{ 
		while(arr[j]>=temp && i<j)--j; 
		arr[i]=arr[j]; 
		while(arr[i]<=temp && i<j)++i; 
		arr[j]=arr[i]; 
	} 
	arr[i]=temp; 
	if(i-1>startPos) quick(arr,startPos,i-1); 
	if(endPos>i+1) quick(arr,i+1,endPos); 
}

void MSort(int SR[],int TR1[], int s, int t)//定義歸并函數
{
int TR2[NUM];
int m;
if(s==t) 
TR1[s] = SR[s];
else
{
m=(s+t)/2;
MSort(SR,TR2,s,m);
MSort(SR,TR2,m+1,t);
Merge(TR2, TR1,s,m,t);
}
}

void Merge(int SR[],int TR[], int i,int m, int n)
{
int j,k,l;
for(j=m+1,k=i; i<=m&&j<=n; ++k)
{
if( SR[i]<SR[j] )
TR[k] = SR[i++];
else
TR[k] = SR[j++];
}

l=k;
if(i<=m)
for(;k<=n&&i<=m;k++)
TR[k] = SR[i++];
k=l;
if(j<=n)
for(;k<=n&&j<=n;k++)
TR[k] = SR[j++];
}