「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

順番に見ていきましょう。
まずは予備知識として「ソート」について簡単に説明します。
「そんなの説明されなくても知ってるよ！」な人は適当に読み飛ばしてください。

ソートは「何らかの規則に従ってデータを並べること」です。
並べる順番は

・小さい順（昇順）
・大きい順（降順）
・アルファベット順
・五十音順
・古い順
・新しい順
・好きな順
・嫌いな順

など、いろいろ あります。



以上を踏まえて

データを小さい順や大きい順に並べるときの やり方のひとつ

が「挿入ソート」です。

挿入ソートで やることは単純です。

１．「まだ並べ替えてないよ」エリアにあるデータを「もう並べ替えたよ」エリアに移す
２．移すデータは「もう並べ替えたよ」エリアにあるデータの大小関係が ちゃんとなるところに入れる

をデータがなくなるまで繰り返すだけです。

……と言葉で説明されても、イメージしにくいかも しれませんね。

大丈夫です。
例を挙げて説明します。

例えば、そうですね。

「1」から「5」までの数字がバラバラな順番で並んでいました。
これを挿入ソートを使って小さい順に並べ替えます。



最初の時点では、すべてのデータが「まだ並べ替えてないよ」エリアにあると考えます。
「もう並べ替えたよ」エリアは空っぽです。



それでは並べ替えスタートです。
まず、1番左にあるデータ「3」を「もう並べ替えたよ」エリアに移動します。



次に、残っているデータの中で1番左にあるデータ「1」を「もう並べ替えたよ」エリアに移動します。



「1」は「3」より小さいので「3」の左に入れます。



次に、残っているデータの中で1番左にあるデータ「5」を「もう並べ替えたよ」エリアに移動します。



「5」は「3」より大きいので「3」の右に入れます。



次に、残っているデータの中で1番左にあるデータ「2」を「もう並べ替えたよ」エリアに移動します。



「2」は「1」より大きくて「3」より小さいので「1」と「3」の間に入れます。



次に、残ったデータの中から……おっと、もう1つしか残っていませんね。
残っているデータ「4」を「もう並べ替えたよ」エリアに移動します。



「4」は「3」より大きくて「5」より小さいので「3」と「5」の間に入れます。



これで全部の並べ替えが終わりました。



おぉ、ちゃんと小さい順に並びましたね。



これが挿入ソートの基本的な考え方です。

やっていることは単純ですよね。

１．「まだ並べ替えてないよ」エリアにあるデータを1つ取り出す
２．「もう並べ替えたよ」エリアにあるデータの大小関係が ちゃんとなるところに入れる

を繰り返すだけです。

ちなみに、今回の説明では「まだ並べ替えてないよ」エリアと「もう並べ替えたよ」エリアの2つを用意して説明しました。
人によっては2つのエリアに分けないで説明している場合も あります。

せっかくなので、2つのエリアに分けない説明も書いておきますね。

「1」から「5」までの数字がバラバラな順番で並んでいました。
これを挿入ソートを使って小さい順に並べ替えます。



最初の時点では、すべてのデータが並べ替えてない状態です。
分かりやすくするために、並べ替えていないデータは青色で表現しておきますね。



それでは並べ替えスタートです。
まず、1番左にあるデータ「3」を並べ替えたことにします。
並べ替えたデータは緑色で表現しますね。



次に、左から2番目にあるデータ「1」を並べ替えます。



「1」は「3」より小さいので「3」の左に移動します。



これで「1」と「3」が並べ替え済みになりました。



次に、左から3番目にあるデータ「5」を並べ替えます。



「5」は「3」より大きいので移動する必要ありません。
そのままにしておきます。



これで「1」と「3」と「5」が並べ替え済みになりました。



次に、左から4番目にあるデータ「2」を並べ替えます。



「2」は「1」より大きくて「3」より小さいので「1」と「3」の間に移動します。



これで「1」と「3」と「5」と「2」が並べ替え済みになりました。



最後に、一番右にあるデータ「4」を並べ替えます。



「4」は「3」より大きくて「5」より小さいので「3」と「5」の間に移動します。



これで全部の並べ替えが終わりました。



おぉ、ちゃんと小さい順に並びましたね。



少し複雑そうに見えますが、やっていることは前半で説明したのと同じです。

まずは前半で説明した挿入ソートの「考え方」を理解できるように頑張ってください。
考え方を理解できれば、後半で説明したやり方も理解できると思います。