インサーションソート
この用語のポイント
データを小さい順（大きい順）に並べるときの やり方だよ
「まだ並べ替えてないよ」な場所から「もう並べ替えたよ」な場所にデータを移していくよ
「もう並べ替えたよ」な場所の、順番に並ぶところ（大小関係が ちゃんとしているところ）にデータを入れていくよ
簡単に書くよ
インサーションソート（英：insertion sort）とは
「挿入ソート」のこと。
用語の中身としては
バラバラに並んでいるデータを「小さい順」or「大きい順」に並べ替えるやり方のひとつ
であり
「まだ並べ替えてないよ」エリアにあるデータを「もう並べ替えたよ」エリアの「データの大小関係が ちゃんとなるところ」に入れていくことで全体を並べ替えるやり方
です。
詳しく書くよ
順番に見ていきましょう。
まずは予備知識として「ソート」について簡単に説明します。
「そんなの説明されなくても知ってるよ！」な人は適当に読み飛ばしてください。
ソートは「何らかの規則に従ってデータを並べること」です。
並べる順番は
・小さい順（昇順）
・大きい順（降順）
・アルファベット順
・五十音順
・古い順
・新しい順
・好きな順
・嫌いな順
など、いろいろ あります。
以上を踏まえて
データを小さい順や大きい順に並べるときの やり方のひとつ
が「インサーションソート」です。
「挿入ソート」とも呼ばれます。
インサーションソートで やることは単純です。
１．「まだ並べ替えてないよ」エリアにあるデータを「もう並べ替えたよ」エリアに移す
２．移すデータは「もう並べ替えたよ」エリアにあるデータの大小関係が ちゃんとなるところに入れる
をデータがなくなるまで繰り返すだけです。
……と言葉で説明されても、イメージしにくいかも しれませんね。
大丈夫です。
例を挙げて説明します。
例えば、そうですね。
「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」の間に移動します。
これで全部の並べ替えが終わりました。
おぉ、ちゃんと小さい順に並びましたね。
少し複雑そうに見えますが、やっていることは前半で説明したのと同じです。
まずは前半で説明したインサーションソートの「考え方」を理解できるように頑張ってください。
考え方を理解できれば、後半で説明したやり方も理解できると思います。
一言でまとめるよ
まぁ「インサーションソート」って単語が出てきたら「並べ替えのやり方なんだな～」と お考えください。
おまけ
■訳してみるよ
「insertion（インサーション）」の意味は「挿入」とか「差し込み」とか「挿入物」とかです。
「sort（ソート）」の意味は「並べ替える」とかです。
何となく くっつけると
挿入して並べ替える
となります。
■検索してみる？
