挿入ソート

Infobox algorithm

classソート

image--FileInsertionsort-editedpngnone280pxExample of insertion sort sorting a list of random numbers--

caption--Example of insertion sort sorting a list of random numbers--

data配列

timensup2sup
best-timeOn
average-timensup2sup
spacen total O1 auxiliary
optimalNo

挿入ソート(インサーションソート)は、ソートのアルゴリズムの一つ。整列してある配列に追加要素適切場所に挿入すること。平均計算時間・最悪計算時間がともにランダウの記号Onsup2supと遅いが、アルゴリズムが単純実装が容易なため、しばしば用いられる。安定ソート安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。

挿入ソート高速化したソート法として、シェルソートが知られている。

アルゴリズム

まず1番目と2番目の要素を比較し、順番が逆であれば入れ換える。次に、3番目の要素が2番目までの要素より小さい場合、正しい順に並ぶように挿入する(配列の場合、前の要素を後ろに一つずつずらす)。この操作で、3番目までのデータが整列済みとなる(ただし、さらにデータが挿入される可能性があるので確定ではない)。このあと、4番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。

C言語による実装例
For文for i 1 i n i
tmp datai
if datai - 1 tmp
j i
do
dataj dataj - 1
j--
while j 0 dataj - 1 tmp
dataj tmp


動作例

整列された部分(確定とは限らない)をアンダーライン、挿入する部分を太字で表す。

-
8 4 3 7 6 5 2 1 (初期データ)
-

styletext-decorationunderline 4 styletext-decorationunderline 8 3 7 6 5 2 1 (1回目のループ終了時)

-

styletext-decorationunderline 3 styletext-decorationunderline 4 styletext-decoration underline 8 7 6 5 2 1 (2回目のループ終了時)

-

styletext-decorationunderline 3 styletext-decorationunderline 4 styletext-decorationunderline 7 styletext-decorationunderline 8 6 5 2 1 (3回目のループ終了時)

-

styletext-decorationunderline 3 styletext-decorationunderline 4 styletext-decorationunderline 6 styletext-decorationunderline 7 styletext-decorationunderline 8 5 2 1 (4回目のループ終了時)

-

styletext-decorationunderline 3 styletext-decorationunderline 4 styletext-decorationunderline 5 styletext-decorationunderline 6 styletext-decorationunderline 7 styletext-decorationunderline 8 2 1 (5回目のループ終了時)

-

styletext-decorationunderline 2 styletext-decorationunderline 3 styletext-decorationunderline 4 styletext-decorationunderline 5 styletext-decorationunderline 6 styletext-decorationunderline 7 styletext-decorationunderline 8 1 (6回目のループ終了時)

-

styletext-decorationunderline 1 styletext-decorationunderline 2 styletext-decorationunderline 3 styletext-decorationunderline 4 styletext-decorationunderline 5 styletext-decorationunderline 6 styletext-decorationunderline 7 styletext-decorationunderline 8 (7回目のループ終了時。ソート完了)

計算時間

バブルソートと比較すると、交換回数は等しくなる。しかし、比較回数は、バブルソートでは必ずnn-1 2回必要だったが、挿入ソートはこれ以下で済むため、挿入ソートの方が高速である。また、ほとんど整列済みのデータに対しては高速という特徴を持っている。

なお交換回数に関しても、前記実装例のように一連の交換の途中の特定処理を省略することができるので交換一回が高速になる。また、特にデータが連結リストで格納されている場合には、バブルソートと比較して大幅な高速化が図れる。これは配列における挿入が一連の交換(の途中の特定処理を省略した処理)によって実現されるのに対し、連結リストでは文字通りの挿入が可能であるので、交換回数が大幅に減少するからである。

二分挿入ソート

挿入ソートの改良で、挿入するデータの前ではソートが済んでいるという性質を利用して、挿入する箇所を二分探索するというものである。データの量が少ないときにはあまり効果がないが、多いときには比較回数が少なくなる。探索アルゴリズムによっては不安定なソートになるが、工夫により安定させることが可能である。

ソート
Categoryソートそうにゆうそおと
noSorteringsalgoritmeInnstikksortering