少しでも分かりやすく伝えたい挿入ソート

少しでも分かりやすく伝えたい挿入ソート

こんにちは、しゃねろんです。
今回はソートの中でも選択ソートと同じくらい構造が簡単な挿入ソートについて説明していきます。
他にも選択ソートやヒープソートといったソートに関する記事も書いているので良かったら見ていってください!

挿入ソートとは

まず、ソート(sort)の意味自体はデータの大小等を比較し並べ替える事を言いますが、今回説明する挿入ソートはズバリ言うと、最初のデータを左端においてデータ比較をしながらソートを行っていくアルゴリズムのことです。

挿入ソートのやり方

まあ上の説明だけではパッとしない方も多いと思うので早速挿入ソートのソート手順について説明していきたいと思います!

1.データを用意する

選択ソート同様にまずはソートするデータを用意します。

挿入ソートするデータ

今回は上のようなデータを用意しました。このデータを基にソートを行っていきます!

2.最初のデータは左端に置く

最初のデータは左端におきます。文の通りです。

最初のデータは左端に置く

つまり、このステップでは並べ替えは行いません。

3.隣のデータを前のデータと比較する

今回だと隣のデータというのは「3」を示します。これと前のデータの「7」と比較していきます。
当然ですが、「3 < 7」なので「3」の方が小さいですね。
こういった場合は、「3」を「7」の前に挿入する形で並べ替えを行います。

挿入ソートによる並べ替え1

「7」の前に「3」が挿入されました。

後はこれを繰り返していくことで、挿入ソートによる並べ替えを行うことができます。

次に「2」です。これも前回と同様に前のデータと比較していきます。
「2 < 7」なので「7」より小さい(左側の)データであることが分かりました。現段階では「7」より小さい事しかわかっていないので、更に前のデータと比較していきます。
「2 < 3」なので「3」より小さい(左側の)データであることが分かりました。これより前のデータはないので「3」の前に「2」を挿入します。

挿入ソートによる並べ替え2

要約すると上の画像のようになります。

次に「8」です。
前のデータ「7」と比較しますが「7 < 8」と前のデータより大きい値ですね。

挿入ソートによる並べ替え3

こういった場合はどこかに挿入はせず、次の値に進みます。

次は「12」です。

挿入ソートによる並べ替え4

とはいっても、「8」の時と同様に、前の値より大きいので次の値に進みます。

次に「5」です。
前の値とそれぞれ比較していき、「3 < 5 < 7(3より大きくて7より小さい)」ことが比較していくと分かると思います。

挿入ソートによる並べ替え5

「3」と「7」の間に「5」を挿入します。

最後に「9」です。
「5」の時と同様に前の値とそれぞれ比較していき、「8 < 9 < 12(8より大きくて12より小さい)」ことが比較していくと分かると思います。

挿入ソートによる並べ替え6

「8」と「12」の間に「9」を挿入します。

これで昇順にソートすることができました。

まとめ

今回は挿入ソートについて説明してきました。前の値と比較をしていき、適切な場所に値を挿入していくことでソートを進めていきます。
他にも選択ソートやマージソート、クイックソートといったソートの方法もあるので是非調べてみてください!

テーマ

現在使用中テーマは最新版

v.1.0v.2.0v.3.0v.3.1v.3.2v.3.3v.3.4v.3.5v.3.6v.3.7v.3.8v.shaneron選択しない(安定版)