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


void print(int *p,int begin,int end)
{
	int count=0;
	int i;
	for(i=begin-1;i<end;i++){
		printf("%d	",*(p+i));
		count++;
		if(count%10==0)
		printf("\n");
	}
}


int *BuildArray(int n)
{
	int k;
	int *p;
	p=Queue;
	srand((unsigned)time(NULL));
	for(k=0;k<n;k++){
		*(p+k)=rand()%MAX;		//隨即生成數組元素
	}
	return p;
}


void swap(int *p1,int *p2)
{
	int temp;
	temp=*p1;
	*p1=*p2;
	*p2=temp;
	if(move==LIMIT){
		move=0;
		m_carry++;
	}
	move+=3;	
}


void crheap(int *p,int n,int s)			//建堆
{
	int temp,num_S,num_C;
	temp=*(p+s);				//臨時存放開始元素
	if(move==LIMIT){
		move=0;
		m_carry++;
	}
	move++;
	num_S=s;				//開始元素下標
	num_C=2*num_S+1;
	while(num_C<n){
		if(num_C<n-1&&*(p+num_C)<*(p+num_C+1))	//取2子節點較大者
		num_C++;
		if(compare==LIMIT){
			compare=0;
			c_carry++;
		}
		compare++;
		if(temp<*(p+num_C)){			
			if(compare==LIMIT){
				compare=0;
				c_carry++;
			}
			compare++;
			*(p+num_S)=*(p+num_C);
			if(move==LIMIT){
				move=0;
				m_carry++;
			}
			move++;
			num_S=num_C;
			num_C=2*num_S+1;
		}
		else{
			if(compare==LIMIT){
				compare=0;
				c_carry++;
			} 
			compare++;
			break;
		}		
	}
	*(p+num_S)=temp;
	if(move==LIMIT){
		move=0;
		m_carry++;
	}
	move++;	
}


int Median3(int *p,int Left,int Right)
{
	int Center=(Left+Right)/2;
	if(*(p+Left)>*(p+Center)){
		if(compare==LIMIT){
			compare=0;
			c_carry++;
		}
		compare++;
		swap(p+Left,p+Center);
	}
	if(*(p+Left)>*(p+Right)){
		if(compare==LIMIT){
			compare=0;
			c_carry++;
		}
		compare++;
		swap(p+Left,p+Right);
	}
	if(*(p+Center)>*(p+Right)){
		if(compare==LIMIT){
			compare=0;
			c_carry++;
		}
		compare++;
		swap(p+Center,p+Right);
	}
	swap(p+Center,p+Right-1);
	return *(p+Right-1);
}


void BubbleSort(int *p,int n)
{
	int i,j;
	for(i=0;i<n-1;i++){
		for(j=n-1;j>=i+1;j--){			//j從后向前掃描
			if(*(p+j)<*(p+j-1)){
				swap((p+j),(p+j-1));	//交換與要求順序相反的相鄰2個數
			}
			if(compare==LIMIT){		//判斷計數是否溢出，下同
				compare=0;
				c_carry++;
			}
			compare++;
		}
	}
}


void HeapSort(int *p,int n)
{
	int i,k;
	for(i=n/2-1;i>=0;i--)
		crheap(p,n,i);
	for(k=n-1;k>=1;k--){
		swap(p+0,p+k);
		crheap(p,k,0);
	}
}


void InsertSort(int *p,int n)
{
	int i,j,temp;
	for(i=1;i<n;i++){		
		temp=*(p+i);
		if(move==LIMIT){
			move=0;
			m_carry++;
		}
		move++;
		for(j=i-1;j>=0;j--){
			if(temp>=*(p+j))
				break;
			else{ 
				*(p+j+1)=*(p+j);
				if(move==LIMIT){
					move=0;
					m_carry++;
				}
				move++;
			}
			if(compare==LIMIT){
				compare=0;
				c_carry++;
			}
			compare++;
		}
		*(p+j+1)=temp;
		if(move==LIMIT){
			move=0;
			m_carry++;
		}
		move++;
	}
}


void QuickSort(int *p,int n,int Left,int Right)
{
	int i,j;
	int Pivot;
	if(Left+2<=Right){
		Pivot=Median3(p,Left,Right);
		i=Left;j=Right-1;
		for(;;){
			while(*(p+(++i))<Pivot){
				if(compare==LIMIT){
					compare=0;
					c_carry++;
				}
				compare++;
			}
			while(*(p+(--j))>Pivot){
				if(compare==LIMIT){
					compare=0;
					c_carry++;
				}
				compare++;
			}
			if(i<j){
				swap((p+i),(p+j));
			}
			else break;
		}
		swap((p+i),(p+Right-1));
		QuickSort(p,n,Left,i-1);
		QuickSort(p,n,i+1,Right);
	}
	else{
		(*(p+Left)<*(p+Right))?:swap((p+Left),(p+Right));
		if(compare==LIMIT){
			compare=0;
			c_carry++;
		}
		compare++;
	}
}


void SelectSort(int *p,int n)
{
	int i,j;
	int min,temp;
	for(i=0;i<n-1;i++){
		min=i;
		for(j=i+1;j<n;j++){
			if(*(p+j)<*(p+min)){
				min=j;
			}
			if(compare==LIMIT){
				compare=0;
				c_carry++;
			}
			compare++;
		}
		if(min!=i){
			swap(p+i,p+min);
		}
	}
}


void ShellSort(int *p,int n)
{
	int i,j;
	int temp,increment;
	for(increment=n/2;increment>0;increment/=2){
		for(i=increment;i<n;i++){
			temp=*(p+i);
			if(move==LIMIT){
				move=0;
				m_carry++;
			}
			move++;
			for(j=i;j>=increment;j-=increment){
				if(temp<*(p+j-increment)){
					if(compare==LIMIT){
						compare=0;
						c_carry++;
					}
					compare++;
					*(p+j)=*(p+j-increment);
					if(move==LIMIT){
						move=0;
						m_carry++;
					}
					move++;
				}
				else{
					if(compare==LIMIT){
						compare=0;
						c_carry++;
					}
					else
						compare++;
					break;
				}
			}
			*(p+j)=temp;
			if(move==LIMIT){
				move=0;
				m_carry++;
			}
			move++;
		}
	}		
}

//檢查排序之后數組是否正確
void check(int *p,int n)
{
	int i;
	for(i=0;i<n;i++){
		if(*(p+i)>*(p+i+1))
			printf("sorted queue is wrong!plaese check the algorithm!\n");
			break;
		if(*(p+i)<=*(p+i+1)){}
	}
	printf("sorted queue is correct!\n");
}

//初始化一些計數變量和輔助數組
void	initializtion(int n)
{
	int i;
	pt=a;
	compare=0;move=0;
	c_carry=0;m_carry=0;
	memset(a,0,sizeof(a));
	for(i=0;i<n;i++)
		*(pt+i)=*(ptr+i);	
}