InsertionSort（挿入ソート：基本挿入法）（C言語編）

InsertionSort（挿入ソート：基本挿入法）のC言語による実装

#include "insertion.h"

void insertionsort(int *array,int size){
	int i,j,k;
	int temp;
	// 挿入対象ごとに繰り返し
	for(i=0;i<size;i++){
		// 挿入位置を探索
		for(j=0;j<i;j++)
			if(array[i] < array[j]) break;

		// 入れ替え
		temp=array[i];
		for(k=i;j<k;k--)array[k]=array[k-1];
		array[j]=temp;
	}
}

配列を使って実現しているので，非常に効率が悪い．
リストを使うと，後半の「入れ替え」部分の計算量がO(1)になる．