このソートアルゴリズムは、ソート済みの集合体の中からソートする値を適切な位置に挿入していくアルゴリズムです。ちょうど、トランプの手札を並べ替えるような感じでソートされます。
単純挿入法(Insertion Sort)は安定しているソートアルゴリズムです。
- 集合体の2番目の値の場所から最後まで、以下を繰り返す。先頭はソート済みとみなす。
- 決定項の初期値を、現在のソート対象位置の値を代入する。
- ソート済みの集合体の中から、入れるべき場所を探し、場所を空ける。
- 空けた場所に決定項を代入する。
*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--)
のように、判定条件を変更すると降順になります。今回のサンプルソースは昇順です。