1.単純挿入法(Insertion Sort)とは
このソートアルゴリズムは、ソート済みの集合体の中からソートする値を適切な位置に挿入していくアルゴリズムです。
ちょうど、トランプの手札を並べ替えるような感じでソートされます。
単純挿入法(Insertion Sort)は安定しているソートアルゴリズムです。
ちょうど、トランプの手札を並べ替えるような感じでソートされます。
単純挿入法(Insertion Sort)は安定しているソートアルゴリズムです。
2.単純挿入法(Insertion Sort)の実装
1.集合体の2番目の値の場所から最後まで、以下を繰り返す。先頭はソート済みとみなす。
2.決定項の初期値を、現在のソート対象位置の値を代入する。
3.ソート済みの集合体の中から、入れるべき場所を探し、場所を空ける。
4.空けた場所に決定項を代入する。
*ptrはint型変数の配列への先頭ポインタ、nはデータの個数です。
void insertion_sort(int *ptr, int n)
{
int i, j, k;
for(i=1; i<n; i++){
k = *(ptr+i);
for(j = i-1; j >=0 && k<*(ptr+j); j--){
*(ptr+j+1) = *(ptr+j);
}
*(ptr+j+1) = k;
}
}
また、
for(j = i-1; j >=0 && k<*(ptr+j); j--){
を
for(j = i-1; j >=0 && k>*(ptr+j); j--)
のように、判定条件を変更すると降順になります。
今回のサンプルソースは昇順です。