こんにちは、Torusです。
今回の目標
以下の知識が得られることを目標とします！
- 挿入ソートとはどのようなアルゴリズムであるか？
- 実行手順
- C言語における記述
挿入ソートとはどのようなアルゴリズムであるか？
まずは抽象的に説明しますが、後でちゃんと一つ一つ説明するので安心して下さい。
挿入ソートとは、配列の要素を一つずつ取り出し、既にソートされた部分に適切に挿入していくことで、配列全体を昇順もしくは降順に並び替えるアルゴリズムです。
上記の文章だけ見て、「フムフムなるほどな!」となる人はそうそういないのではないでしょうか？
順を追って説明していきます。例として、下記の数の入ったブロックの図のようなものをソートしたいとします。
今は「3, 1, 4, 2」と並んでいる訳ですが、最終的には、「1, 2, 3, 4」という風に並び替えたい訳です。
これを昇順にソートすると言います。左から右へ昇っていくイメージです。
逆に、「4, 3, 2, 1」という風に並び替えることを降順にソートすると言います。これも同様に、
左から右へ降りていくイメージです。
実際の実行手順
それでは、まず実行手順の大枠をお話します。より詳細な話は後でするので、無理に理解しようとせずに気楽に見て下さい。
注意事項として一番左のブロックは0番目のブロックとし、最後のブロックをn番目のブロックとします。また、議論を簡単にするため、ソートするブロックは全て異なる数のブロックであることとします。
A. 基準値を0~n番目まで順次変更して以降の処理を繰り返し、n番目までの比較が終わったらアルゴリズムを終了する。
1. 0番目からi-1番目までが整列済みブロックであるならば、基準値をi番目とする。
B. 基準値の値が定まり処理が終了するまで2の処理を繰り返し行う。
2. i番目の基準値と整列済みブロックとで大小比較を行う。このとき、大小比較について、i-1, i-2, i-3, …, 0の順で基準値と比較を行う。大小比較の結果によって、以下のような処理を実行していく。
2.1 (基準値より小さい値がない場合) 基準値とソート済みブロック全てを比較した結果、ソート済みブロックの中に基準値より小さい値がなかったときは基準値のブロックを先頭に入れて、B.の処理を終了し、Aに戻る。
2.2 (基準値の方が値が小さい場合) 基準値とk番目のブロックを比較した結果、基準値の方が値が小さいならばk+1番目ブロックの値をk番目のブロックの値にする。ただし、k=0のときは2.1の処理を行う。
2.3 (基準値の方が値が大きい場合) 基準値とk番目のブロックを比較した結果、基準値の方が値が大きいならばk+1番目ブロックの値を基準値のブロックの値にし、B.の処理を終了し、Aに戻る。
Aの処理について
まず、基準値の説明をします。唐突ですが皆さんに質問です。下記の図を見て下さい。
左側のオレンジのブロック1, 4は昇順に整列済みとします。このとき、青のブロック2をどこに差し込めば良いでしょうか？もちろん、1と4の間ですよね。この例のようにどこに差し込むかを決めようとしているブロックを基準値と言います。実際の処理では、この基準値を一番左のブロックから一番右のブロックに順次変更していきます。
Bの処理について
Bの処理は具体的に基準値をどこに差し込むかを決定する処理です。その処理が2.1~2.3の3パターンに分かれているだけです。それでは一つずつ見ていきましょう。
2.1 (基準値より小さい値がない場合)の処理について
下記の図を見て下さい。
左側のオレンジのブロック3, 7は昇順に整列済みとします。このとき、基準値である青のブロック1をどこに差し込めば良いでしょうか？答えは、先頭ですよね。この理由を言語化すると、整列済みのブロックと基準値となるブロックの中で一番値の小さいブロックが基準値だからです。
2.2 (基準値の方が値が小さい場合)の処理について
次も先程と同じ例を使いますが、分かりやすさのため、あえてソートしたいブロック列の方では基準値1の部分もオレンジ色のブロックにして、青ブロックの基準値を別で用意します。
青ブロックと整列済みブロックである3, 7を比較します。より具体的には、整列済みブロックの一番右側である7から比較します。基準値1と7を比較すると基準値1の方が小さいので、このときは、7を右側のブロックへコピーします。つまり、下記の図のようになります。
ここで皆さんの中で「なぜ上記のようなコピーをするのか」という疑問が生まれるかもしれません。このようなコピーをする理由として、気持ち的にはコピーではなくて下記の図のように右側に数をスライドさせたいという背景があります。
ただ、あえて真ん中のブロックのデータを消す手間を掛ける必要がないのでコピーします。
次に、基準値1と3を比較すると、基準値1の方が小さいので、3を右側のブロックへコピーします。つまり、下記の図のようになります。
先程と同様に気持ちとしては下記の図のようになります。
全て比較し終わって先頭まで来てしまったので、2.1の手順の通り、先頭に基準値を入れてBの処理は終了です。
2.3 (基準値の方が値が大きい場合)の処理について
左側のオレンジのブロック1, 4は昇順に整列済みとします。このとき、青のブロック2の差し込み手順を考えましょう。
まず、基準値2と4を比較すると、基準値2の方が小さいので、4を右側のブロックへコピーします。つまり、下記の図のようになります。
気持ちとしては下記の図のようになります。
次に、基準値2と1を比較すると、基準値2の方が大きいので、1の右側に基準値を入れてBの処理は終了です。
C言語における記述
main関数は書かないで、挿入ソートの関数部分だけ解説します。挿入ソート関数は以下のように記述出来ます。
void sort(int data[], int n){
int i, j, base, num;
for(i=1;i<n;i++){
base=data[i];
for(j=i-1;j>=0;j--){
num=data[j];
if(base<num) data[j+1]=num;
else{
data[j+1]=base;
break;
}
}
if(j==-1) data[0]=base;
}
return;
}
まず、関数sortの引数について説明します。data[]はソートするブロック達の中の数字、すなわち、ブロック達そのものを表す配列と言っても良いでしょう。nはデータ数、すなわち、ブロックの数です。また、このアルゴリズムで用いられている文字であるbaseは基準値であり、numは基準値と比較する数になります。
今まで学んできたものとコードを見比べて理解を深めて下さいね。
では、また！