苗火 Nicholas

[Data Structures] Insertion sort

2019-4-25 萧 写技术

#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");

}

标签: Data Structures