# Sort algorithm
## Merge Sort Array

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

void merge(int a[],int l,int m,int r){
	int n1=m-l+1;
	int n2=r-m;
	int L[n1];
	int R[n2];
	int i,j;
	for(i=0;i<n1;i++)
		L[i]=a[l+i];
	for(j=0;j<n2;j++)
		R[j]=a[(m+1)+j];	//from m+1 to (m+1)+j

	i=0;
	j=0;
	while(i<n1 && j<n2){
		if(L[i]<R[j]){
			a[l]=L[i];
			l++;
			i++;
		}
		else {
			a[l]=R[j];
			l++;
			j++;
		}
	}
	while(i<n1){//left have 
		a[l]=L[i];
		l++;
		i++;
	}
	while(j<n2){//right have 
		a[l]=R[j];
		l++;
		j++;
	}
	
	
}
void merge_sort(int a[],int l,int r){
	if(l<r){
	int mid=l+(r-l)/2;
	//divide
	merge_sort(a,mid+1,r);
	merge_sort(a,l,mid);
	//merge;
	merge(a,l,mid,r);
	}
}
	
int main()
{	int a[]={12,11,13,5,6,14};

	//printf("%d\n",sizeof(a)/sizeof(a[0]));
	int size=sizeof(a)/sizeof(a[0]);
	
	merge_sort(a,0,size-1);
	
	for(int i=0;i<size;i++){
		printf("%d ",a[i]);
	}
	return 0;
}

## Quick Sort Array

#include<stdio.h>
	
void swap(int *a,int *b ){
	int temp=*a;
	*a=*b;
	*b=temp;
}
int partition(int a[],int low,int high){
	int pivot=a[high];
	int i=low-1;// Index of smaller element 
	
	
	for(int j=low;j<=high-1;j++){//Traverse elements from j = low to high-1
		// If current element is smaller than the pivot 
		if(a[j]<pivot){
			i++;
			swap(&a[i],&a[j]);// increment index of smaller element 
		}
	}
		swap(&a[i+1],&a[high]);
	
	return i+1;
}
void quick_sort(int a[],int low,int high){
	if(low<high){
	
	//divide
	int pivot=partition(a,low,high);
	
	quick_sort(a,pivot+1,high);
	quick_sort(a,low,pivot-1);
	}
}
int main()
{	int a[]={10,5,1,5,6};

	printf("%d\n",sizeof(a)/sizeof(int));
	int size=sizeof(a)/sizeof(int);
	
	quick_sort(a,0,size-1);
	
	for(int i=0;i<size;i++){
		printf("%d ",a[i]);
	}
	return 0;
}

## Heap Sort Array

#include<stdio.h>
#include<stdlib.h>
void swap(int *a,int *b){
	int tmp=*a;
	*a=*b;
	*b=tmp;
}


void heapify(int arr[],int n,int i){//6,
	int max_index=i;
	int l=2*i+1;
	int r=2*i+2;
	if(l<n&&arr[max_index]<arr[l]){
		max_index=l;
	}
	if(r<n&&arr[max_index]<arr[r]){
		max_index=r;
	}
	if(max_index!=i){
		swap(&arr[max_index],&arr[i]);
		heapify(arr,n,max_index);//最大值的位置改到max_index
	}
}
void heap_sort(int arr[],int n){//6
	for(int i=n/2-1;i>=0;i--){
		heapify(arr,n,i);
	}
	for(int i=n-1;i>0;i--){
		swap(&arr[0],&arr[i]);
		heapify(arr,i,0);
	}
}
	
	
int main()
{	int a[]={12,11,13,5,6,14};

	//printf("%d\n",sizeof(a)/sizeof(a[0]));
	int size=sizeof(a)/sizeof(a[0]);
	
	heap_sort(a,size);
	
	for(int i=0;i<size;i++){
		printf("%d ",a[i]);
	}
	return 0;
}

## Selection Sort Array

#include<stdio.h>
#include<stdlib.h>
void swap(int *a,int *b){
	int tmp=*a;
	*a=*b;
	*b=tmp;
}

void select_sort(int arr[],int size){//4
	int i,j;
	int min;
	for(i=0;i<size-1;i++){//0,3
		min=i;
		for(j=i;j<size;j++){
			if(arr[j]<arr[i]){
				min=j;//找出unsorted中，最小的位置
			swap(&arr[min],&arr[i]);	//對unsorted的第一個位置做交換
			}
		}
	}
	
}
	
	
int main()
{	int a[]={9,1,5,6};

	//printf("%d\n",sizeof(a)/sizeof(a[0]));
	int size=sizeof(a)/sizeof(a[0]);
	
	select_sort(a,size);
	
	for(int i=0;i<size;i++){
		printf("%d ",a[i]);
	}
	return 0;
}

## Bubble Sort Array

#include<stdio.h>
#include<stdlib.h>
void swap(int *a,int *b){
	int tmp=*a;
	*a=*b;
	*b=tmp;
}
void bubble_sort(int arr[],int size){//4
	for(int i=0;i<size-1;i++){//排序的次數=4-1
		for(int j=0;j<size-i-1;j++){//排序一個需要的移動次數=4-i-1，-1是因為for裡面有swap((arr+j),(arr+j+1));
			if(arr[j]>arr[j+1]){//把大的放右邊
			swap((arr+j),(arr+j+1));
			//swap(&arr[i],&arr[j]);
			}
		}
	}
}

int main()
{	int a[]={9,1,5,6};
	printf("%d\n",sizeof(a)/sizeof(int));
	int size=sizeof(a)/sizeof(int);
	
	bubble_sort(a,size);
	for(int i=0;i<size;i++){
		printf("%d ",a[i]);
	}
	return 0;
}

## qsort()在C語言
是 **#include <stdlib.h>** 中的一個function。
### h3使用方法
以下方的變數作介紹， **base** 是想要排序的序列，可以放入array的形式， **nitems**是裡面含有多少的元素， **size**是指資料的儲存形式，例如:int。

**compar**是比較的規則，傳入一個int function，利用兩數字相減作為判斷依據。

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*)

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

int values[] = { 88, 56, 100, 2, 25 };

int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );//>0,=0,<0
}

int main()
{
   int n;

   printf("Before sorting the list is: 
");
   for( n = 0 ; n < 5; n++ ) {
      printf("%d ", values[n]);
   }

   qsort(values, 5, sizeof(int), cmpfunc);
//void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

   printf("
After sorting the list is: 
");
   for( n = 0 ; n < 5; n++ ) {
      printf("%d ", values[n]);
   }
  
  return(0);
}