[アルゴリズム] 挿入ソートの実装(解説編)

Pocket
LINEで送る
GREE にシェア
LinkedIn にシェア

アルゴリズムをプログラムしてみるシリーズ第3弾は「挿入ソート(insert-sort)」です。
以前の2つをやった感じだとこのソート方法は、かなりスタンダードな手法であることがわかります。
「選択ソート」よりも少し非効率ではないかと思われるこの挿入ソートですが、今回はアルゴリズム解説を行うので、しっかり学習しましょう(オレ)。

wikipedia

解説

横一列に並んだ乱数値を、左から小さい順に並べることを目的とします。
挿入ソートは左側の数値を順に確定していく単純なやり方ですが、確定した数字の中の適正ポジションに挿入していくイメージです。

1. ランダム数値の配列※左から数値が小さくなるように整列する

%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2017-01-11-23-41-49

2. 左端の2つの数値を比較して左が小さくなるように並び替える

%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2017-01-11-23-41-54

3. 次に左の2つの数値に入る位置に挿入する

%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2017-01-11-23-42-04

4. この場合は、一番小さいので一番左側になる

%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2017-01-11-23-42-12

5. 次に左の確定組と次の数値を比較する

%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2017-01-11-23-42-17

6. 適正な位置に挿入する

%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2017-01-11-23-42-23

7. 比較する数値が一番大きい場合は変更なしになる

%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2017-01-11-23-42-28

8. 全ての数値が確定するまで順に繰り返す

%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2017-01-11-23-42-39

特性

この挿入ソートの特徴は、平均値も最大値も、他のソートアルゴリズムと比べると大きくなり非効率と思われるが、アルゴリズムの難易度が他と比べると優しい為、よく用いられがちだ。
しかし、アルゴリズムで分かりやすいのとプログラムでコーディングしやすいは、決して同じではないかもしれない。
それも踏まえて今回も言語別に構築してみるとしよう。

関連リンク

挿入ソート

解説

アルゴリズム過去記事

http://wordpress.ideacompo.com/?cat=562&tag=Algorithm

Leave a Reply

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です