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