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

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

解説

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

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

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

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

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

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

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

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

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

特性

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

関連リンク

いろいろなプログラム言語でアルゴリズム学習

• 解説
• Javascript
• PHP
• Python
• Shell
• AWK
• C言語
• Go言語
• Ruby