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

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です