#include <stdio.h>

#include <stdlib.h>



/* Straight insertion sort */

void straightInsertionSort(int seq[], int n)

{

	int i;

	int j;

	int tmp;

	for (i=1; i<n; i++) {//From 1

		tmp = seq[i];//Store yourself

		for (j=i-1; j>=0 && seq[j]>seq[i]; j--) {//Compare before, and back one by one while little than it.

			seq[j+1] = seq[j];	

		}

		seq[j+1] = tmp;//Insert

	}

}



/* Binary insertion sort */

void binaryInsertionSort(int seq[], int n)

{

	int i;

	int j;

	int tmp;

	int low;

	int high;

	int mid;

	for (i=1; i<n; i++) {//From 1

		tmp = seq[i];//Store yourself

		low = 0;

		high = i-1;

		while (low <= high) {

			mid = (low + high) / 2;

			if (seq[mid] < tmp) {

				low = mid + 1;

			} else {

				high = mid - 1;

			}

		}

		for (j=i-1; j>=low; j--) {//The low position is also the bigger number than yourself

			seq[j+1] = seq[j];	

		}

		seq[low] = tmp;//Insert

	}

}



/* 2-way binary insertion sort */

void twoWayBinaryInsertionSort(int seq[], int n)

{

	int i;

	int j;

	int tmp;

	int low;

	int high;

	int mid;



	int *order = malloc( n * sizeof(int) );

	int first;

	int final;	



	order[0] = seq[0];

	first = final = 0;

	for (i=1; i<=n; i++) {//From 1

		if( order[0] > seq[i] ){

			if(first == 0){

				first = n + 1;

			}

			low = first;

			high = n;

			

			if( low == 0 ){

				low = n+1;

			}

			while(low <= high){

				mid = (low + high)/2;

				if(order[mid] < seq[i]){

					low = mid + 1;

				}else{

					high = mid -1;

				}

			}

			for(j=first; j <= high; j++){

				order[j-1] = order[j];

			}

			order[high] = seq[i];



			first = (first - 1) % n;

		}else{

			low = 1;

			high = final;

		

			while(low <= high){

				mid = (low + high)/2;

				if(order[mid] < seq[i]){

					low = mid + 1;

				}else{

					high = mid -1;

				}

			}

			for(j=final; j >= low; j--){

				order[j+1] = order[j];

			}

			order[low] = seq[i];

	

			final++;

		}

	}





	for(i=0;i<n;i++){

		seq[i] = order[i];

	}



	free(order);

}



/* Link insertion sort */

typedef struct _NODE{

	int data;

	struct _NODE *next;

}NODE;

#define MAX 65535

void linkInsertionSort(int seq[], int n){

	NODE *link = malloc( (n+1) * sizeof( NODE ) );

	int i;

	int p;

	int q;

	NODE tmp;



	for(i=1; i<=n; i++){

		link[i].data = seq[i-1];

		link[i].next = -1;

	}

	link[0].data = MAX;

	link[0].next = 1;

	link[1].next = 0;



	p = link[0].next;

	q = 0;

	for(i=2;i<=n;i++){

		while(link[p].data<link[i].data){

			q = p;

			p = link[p].next;

		}	

		link[i].next = p;

		link[q].next = i;

		

		p = link[0].next;

		q = 0;

	}



	p = link[0].next;

	for(i=1;i<=n; i++){

		while(p<i){

			p = link[p].next;

		}

		q = link[p].next;

		if(p != i){

			tmp = link[i];

			link[i] = link[p];

			link[p] = tmp;	



			link[i].next = p;

		}

		p = q;

	}





	for(i=0; i<n; i++){

		seq[i] = link[i+1].data;

	}

}



/* Shell sort */

void insertSort_gap(int seq[], int n, int start, int gap)

{

	int i;

	int j;

	int tmp;

	for (i=start + gap; i<n; i += gap) {//From 1

		tmp = seq[i];//Store yourself

		for (j=i-gap; j>=0 && seq[j]>seq[i]; j -= gap) {//Compare before, and back one by one while little than it.

			seq[j+gap] = seq[j];	

		}

		seq[j+gap] = tmp;//Insert

	}

}



void ShellSort(int seq[], int n, int d[], int m)

{

	int i;

	int start;

	int gap;

	for (i = m - 1; i >= 0; i--) {

		gap = d[i];

		for (start = 0; start < gap; start++) {

			insertSort_gap(seq, n, start, gap);

		}

	}	

}



void main()

{

	int ancient[] = {1,9,1,2,3,4,4,5,5,7,8,9,10};

	int seq[] = {1,9,1,2,3,4,4,5,5,7,8,9,10};

	int n = sizeof(seq)/sizeof(int);

	int i;

	int is;



	printf("log.anycle.com\n");



	printf("Simple insertion sort: \n");

	printf("Seq:\n");

	for (i=0; i<n; i++) {

		seq[i] = ancient[i];

		printf(" %2d", seq[i]);

	}	

	printf("\n");

	straightInsertionSort(seq, n);

	for (i=0; i<n; i++) {

		printf(" %2d", seq[i]);

	}	

	printf("\n");





	printf("Binary Insert sort: \n");

	printf("Seq:\n");

	for (i=0; i<n; i++) {

		seq[i] = ancient[i];

		printf(" %2d", seq[i]);

	}	

	printf("\n");

	binaryInsertionSort(seq, n);

	for (i=0; i<n; i++) {

		printf(" %2d", seq[i]);

	}	

	printf("\n");





	printf("2 way binary Insert sort: \n");

	printf("Seq:\n");

	for (i=0; i<n; i++) {

		seq[i] = ancient[i];

		printf(" %2d", seq[i]);

	}	

	printf("\n");

	twoWayBinaryInsertionSort(seq, n);

	for (i=0; i<n; i++) {

		printf(" %2d", seq[i]);

	}	

	printf("\n");



	printf("Link insertion sort: \n");

	printf("Seq:\n");

	for (i=0; i<n; i++) {

		seq[i] = ancient[i];

		printf(" %2d", seq[i]);

	}	

	printf("\n");

	linkInsertionSort(seq, n);

	for (i=0; i<n; i++) {

		printf(" %2d", seq[i]);

	}	

	printf("\n");





	int d[] = {1, 2, 4};

	printf("Shell sort: \n");

	printf("Seq:\n");

	for (i=0; i<n; i++) {

		seq[i] = ancient[i];

		printf(" %2d", seq[i]);

	}	

	printf("\n");

	ShellSort(seq, n, d, sizeof(d)/sizeof(int));

	for (i=0; i<n; i++) {

		printf(" %2d", seq[i]);

	}	

	printf("\n");



}