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)になる．