#include "sort.h"
/*All the sorting functions put the biggest number in the last position!*/

/*Bubble sort is bad,because it is O(n2).Avoid it*/
extern int bubble_sort(void* a,size_t len,int num,int (*comp)(void*,void*)){
	int i,j;
	void* temp;
	if(a==NULL){/*Notice that I just detect whether a is NULL, but I don't make sure that num is in the right arrange!*/
		errno=EINVAL;
		return -1;
		}
	if((temp=malloc(len))==NULL){
		errno=ENOMEM;
		return -1;
		}
	for(i=0;i<num;i++)
		for(j=i+1;j<num;j++)
			if(comp(a+len*j,a+len*i)<0){
				memcpy(temp,a+len*i,len);
				memcpy(a+len*i,a+len*j,len);
				memcpy(a+j*len,temp,len);
				}
	free(temp);
	return 0;
	}
/*Linear insertion sort is also bad for the same reason.Avoid it*/
extern int linear_insertion_sort(void* a,size_t len,int num,int (*comp)(void*,void*)){
	int i,j;
	void* temp;
	if(a==NULL){/*Notice that I just detect whether a is NULL, but I don't make sure that num is in the right arrange!*/
		errno=EINVAL;
		return -1;
		}
	if((temp=malloc(len))==NULL){
		errno=ENOMEM;
		return -1;
		}
	for(i=0;i<num;i++)
		for(j=i;j>0 && comp(a+len*(j-1),a+len*j)>0;j--){
			memcpy(temp,a+len*(j-1),len);
			memcpy(a+len*(j-1),a+len*j,len);
			memcpy(a+j*len,temp,len);
			}
	free(temp);
	return 0;
	}
/*Select sort is also bad for the same reason.Avoid it*/
static int max_key(void* a,size_t len,int f,int e,int (*comp)(void*,void*)){
	int i,m=f;

	for(i=f;i<=e;i++)
		if(comp(a+len*i,a+len*m)>0)
			m=i;
	return m;
	}
extern int select_sort(void* a,size_t len,int num,int (*comp)(void*,void*)){
	int i,mm;
	void* temp;

	if(a==NULL){/*Notice that I just detect whether a is NULL, but I don't make sure that num is in the right arrange!*/
		errno=EINVAL;
		return -1;
		}
	if((temp=malloc(len))==NULL){
		errno=ENOMEM;
		return -1;
		}
	for(i=num-1;i>=0;i--){
		mm=max_key(a,len,0,i,comp);
		memcpy(temp,a+len*i,len);
		memcpy(a+len*i,a+len*mm,len);
		memcpy(a+mm*len,temp,len);
		}
	free(temp);
	return 0;	
	}
/*Binary insertion is much faster on average compared to linear insertion.
 *This program is from the book--C Unleashed.
 */
extern int binary_insertion_sort(void* a,size_t len,int num,int (*comp)(void*,void*)){
	unsigned int partition;
	int beg,ipg,end;
	void* temp;

	if(a==NULL){/*Notice that I just detect whether a is NULL, but I don't make sure that num is in the right arrange!*/
		errno=EINVAL;
		return -1;
		}
	if((temp=malloc(len))==NULL){
		errno=ENOMEM;
		return -1;
		}
	for(partition=1;partition<num;partition++){
		beg=ipg=0;
		end=partition-1;
		while(end>=beg){
			ipg=((end+beg)>>1);
			if(comp(a+len*ipg,a+len*partition)>0)end=ipg-1;
			else beg=++ipg;
			}
		if(partition!=(unsigned int)ipg){
			memcpy(temp,a+len*partition,len);
			memmove(a+len*(ipg+1),a+len*(ipg),(partition-ipg)*len);
			memcpy(a+len*ipg,temp,len);
			}
		}
	free(temp);
	return 0;
	}

/*Shell sort is better than the above,it is an improvement,but still bad*/
static void sort_interval(void* a,size_t len,int start,int num,int increment,int (*comp)(void*,void*)){
	int i,j;
	void* temp;
	if((temp=malloc(len))==NULL){
		errno=ENOMEM;
		return;
		}
	for(i=start;i<num;i+=increment)
		for(j=i;j>0 && comp(a+len*(j-1),a+len*j)>0;j-=increment){
			memcpy(temp,a+len*(j-1),len);
			memcpy(a+len*(j-1),a+len*j,len);
			memcpy(a+len*j,temp,len);
			}
	free(temp);
	}
extern int shell_sort(void* a,size_t len,int num,int (*comp)(void*,void*)){
	int i=0,increment=num;

	if(a==NULL){/*Notice that I just detect whether a is NULL, but I don't make sure that num is in the right arrange!*/
		errno=EINVAL;
		return -1;
		}
	do{
		increment=increment/3+1;
		for(i=0;i<increment;i++)sort_interval(a,len,i,num,increment,comp);
		}while(increment>1);
	return 0;
	}

/*Primitive quicksort. This is a bad algorithm for general purposes. Don't use it! If you like,use improved quicksort.*/
extern int quick_sort(void* a,size_t len,int start,int end,int (*comp)(void*,void*)){/*Warning: Maybe 'end' isn't N if you want to sort N items!(N-1 may be right!)*/
	int loc;

	if(a==NULL){/*Notice that I just detect whether 'a' is NULL, but I don't make sure that 'start' and 'end' are in the right arrange!*/
		errno=EINVAL;
		return -1;
		}
	if(start<end){
		int i=start,j=end;
		void* tmp;
		void* pivot=NULL;
		if((pivot=malloc(len))==NULL){
			errno=ENOMEM;
			return -1;
			}
		memcpy(pivot,a+len*start,len);
		if((tmp=malloc(len))==NULL){
			free(pivot);
			errno=ENOMEM;
			return -1;
			}
		for(;;){
			while(comp(a+len*j,pivot)>=0 && j>start)j--;
			while(comp(a+len*i,pivot)<0 && i<end)i++;
			if(i<j){
				memcpy(tmp,a+len*i,len);
				memcpy(a+len*i,a+len*j,len);
				memcpy(a+len*j,tmp,len);
				}
			else{
				loc=j;
				break;
				}
			}
		free(pivot);
		free(tmp);
		quick_sort(a,len,start,loc,comp);
		quick_sort(a,len,loc+1,end,comp);
		}
	return 0;
	}

/*Heap sorting is good sorting.This program is from the book--Data Structure and Algorithm Analysis in C.*/
#define LeftChild(i) (2*(i)+1)
static void PercDown(void* a,size_t len,int i,int N,int (*comp)(void*,void*)){
	int Child;
	void* tmp;
	if((tmp=malloc(len))==NULL){
		errno=ENOMEM;
		return ;
		}
	memcpy(tmp,a+len*i,len);
	for(;LeftChild(i)<N;i=Child){
		Child=LeftChild(i);
		if(Child!=N-1 && comp(a+len*(Child+1),a+len*Child)>0)
			Child++;
		if(comp(tmp,a+len*Child)<0)
			memcpy(a+len*i,a+len*Child,len);
		else break;
		}
	memcpy(a+len*i,tmp,len);
	free(tmp);
	}
extern int heap_sort(void* a,size_t len,int N,int (*comp)(void*,void*)){
	int i;
	void* tmp;

	if(a==NULL){/*Notice that I just detect whether a is NULL, but I don't make sure that 'N' is in the right arrange!*/
		errno=EINVAL;
		return -1;
		}
	if((tmp=malloc(len))==NULL){
		errno=ENOMEM;
		return -1;
		}
	for(i=N/2;i>=0;i--)PercDown(a,len,i,N,comp);/*Build Heap*/
	for(i=N-1;i>0;i--){/*Delete Max*/
		memcpy(tmp,a,len);
		memcpy(a,a+len*i,len);
		memcpy(a+len*i,tmp,len);
		PercDown(a,len,0,i,comp);
		}
	free(tmp);
	return 0;
	}
/*Merge sort is also good.This program is also from the book--Data Structure and Algorithm Analysis in C.*/
static int Merge(void* a,int Lpos,int Rpos,int Rend,size_t len,int (*comp)(void*,void*)){
	int i,Lend=Rpos-1,Num=Rend-Lpos+1,tmppos=Lpos;
	void* tmp;
	tmp=malloc(Num*len);
	if(tmp==NULL){
		errno=ENOMEM;
		return -1;
		}
	while(Lpos<=Lend && Rpos<=Rend){
		if(comp(a+len*Lpos,a+len*Rpos)<=0)memcpy(tmp+len*(tmppos++),a+len*(Lpos++),len);
		else memcpy(tmp+len*(tmppos++),a+len*(Rpos++),len);
		}
	while(Lpos<=Lend)memcpy(tmp+len*(tmppos++),a+len*(Lpos++),len);
	while(Rpos<=Rend)memcpy(tmp+len*(tmppos++),a+len*(Rpos++),len);
	for(i=0;i<Num;i++,Rend--)memcpy(a+len*Rend,tmp+len*Rend,len);
	free(tmp);
	return 0;
	}
static int Msort(void* a,int left,int right,size_t len,int (*comp)(void*,void*)){
	int center;
	if(left<right){
		center=(left+right)/2;
		Msort(a,left,center,len,comp);
		Msort(a,center+1,right,len,comp);
		if(Merge(a,left,center+1,right,len,comp)==-1)return -1;
		}
	return 0;
	}
extern int merge_sort(void* a,size_t len,int N,int (*comp)(void*,void*)){
	if(a==NULL){/*Notice that I just detect whether a is NULL, but I don't make sure that num is in the right arrange!*/
		errno=EINVAL;
		return -1;
		}
	return Msort(a,0,N-1,len,comp);
	}