挿入ソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』
挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。
挿入ソートを高速化したソート法として、シェルソートが知られている。
目次 |
[編集] アルゴリズム
1番目と2番目を比較し、順番が逆であれば入れ換える。次に、3番目の要素を、正しい順に並ぶように「挿入」する。（挿入する際、右側のデータを後ろに一つずつずらす）この操作で、3番目までのデータが整列済みとなる（但し、データが挿入される可能性があるので確定ではない）。このあと、4番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。
[編集] C言語による実装例
for (i = 1; i < n; i++) { tmp = data[i]; for (j = i; j > 0 && data[j-1] > tmp; j--) { data[j] = data[j-1]; } data[j] = tmp; }
[編集] 動作例
初期データ40.45.72.90.11.5.23.34.54
整列された部分（確定とは限らない）をアンダーライン、挿入する部分を太字で表す。
- 4 8 3 7 6 5 2 1 （1回目のループ終了時）
- 3 4 8 7 6 5 2 1 （2回目のループ終了時）
- 3 4 7 8 6 5 2 1 （3回目のループ終了時）
- 3 4 6 7 8 5 2 1 （4回目のループ終了時）
- 3 4 5 6 7 8 2 1 （5回目のループ終了時）
- 2 3 4 5 6 7 8 1 （6回目のループ終了時）
- 1 2 3 4 5 6 7 8 （7回目のループ終了時。ソート完了）
[編集] 計算時間
バブルソートと比較すると、「交換回数」は等しくなる。しかし、「比較回数」は、バブルソートでは必ずn(n-1) / 2回必要だったが、挿入ソートはこれ以下で済むため、挿入ソートの方が高速である。また、殆ど整列済みのデータに対しては高速という特徴を持っている。
[編集] 二分挿入ソート
挿入ソートの改良で、挿入するデータの前ではソートが済んでいるという性質を利用して、挿入する箇所を二分探索するというものである。データの量が少ないときにはあまり効果がないが、多いときには比較回数が少なくなる。探索アルゴリズムによっては不安定なソートになるが、工夫により安定させることが可能である。
