少しでも分かりやすく伝えたい挿入ソート
皆さんこんにちは！！
今回はソートの中でも選択ソートと同じくらい構造が簡単な挿入ソートについて説明していきます。
挿入ソートとは
まず、ソート(sort)の意味自体はデータの大小等を比較し並べ替える事を言いますが、今回説明する挿入ソートはズバリ言うと、最初のデータを左端においてデータ比較をしながらソートを行っていくアルゴリズムのことです。
挿入ソートのやり方
まあ上の説明だけではパッとしない方も多いと思うので早速挿入ソートのソート手順について説明していきたいと思います！
1.データを用意する
選択ソート同様にまずはソートするデータを用意します。
今回は上のようなデータを用意しました。このデータを基にソートを行っていきます！
2.最初のデータは左端に置く
最初のデータは左端におきます。文の通りです。
つまり、このステップでは並べ替えは行いません。
3.隣のデータを前のデータと比較する(繰り返し)
今回だと隣のデータというのは「3」を示します。これと前のデータの「7」と比較していきます。
当然ですが、「3 < 7」なので「3」の方が小さいですね。
こういった場合は、「3」を「7」の前に挿入する形で並べ替えを行います。
「7」の前に「3」が挿入されました。
後はこれを繰り返していくことで、挿入ソートによる並べ替えを行うことができます。
次に「2」です。これも前回と同様に前のデータと比較していきます。
「2 < 7」なので「7」より小さい(左側の)データであることが分かりました。現段階では「7」より小さい事しかわかっていないので、更に前のデータと比較していきます。
「2 < 3」なので「3」より小さい(左側の)データであることが分かりました。これより前のデータはないので「3」の前に「2」を挿入します。
要約すると上の画像のようになります。
次に「8」です。
前のデータ「7」と比較しますが「7 < 8」と前のデータより大きい値ですね。
こういった場合はどこかに挿入はせず、次の値に進みます。
次は「12」です。
とはいっても、「8」の時と同様に、前の値より大きいので次の値に進みます。
次に「5」です。
前の値とそれぞれ比較していき、「3 < 5 < 7(3より大きくて7より小さい)」ことが比較していくと分かると思います。
「3」と「7」の間に「5」を挿入します。
最後に「9」です。
「5」の時と同様に前の値とそれぞれ比較していき、「8 < 9 < 12(8より大きくて12より小さい)」ことが比較していくと分かると思います。
「8」と「12」の間に「9」を挿入します。
これで昇順にソートすることができました。
まとめ
今回は挿入ソートについて説明してきました。前の値と比較をしていき、適切な場所に値を挿入していくことでソートを進めていきます。
他にも選択ソートやマージソート、クイックソートといったソートの記事も紹介しているので合わせてご覧ください！