挿入ソートのソースを表示

{{出典の明記|date=2023年10月}}
{{Infobox algorithm
|class=[[ソート]]
|image=<!--[[File:Insertionsort-edited.png|none|280px|Example of insertion sort sorting a list of random numbers.]]-->
|caption=<!--Example of insertion sort sorting a list of random numbers.-->
|data=[[配列]]
|time=<math>O(n^2)</math>
|best-time=<math>O(n)</math>
|average-time=<math>O(n^2)</math>
|space=<math>O(n)</math> total, <math>O(1)</math> auxiliary
|optimal=No
}}
'''挿入ソート'''（そうにゅうソート、{{lang-en-short|insertion sort}}）あるいは'''基本挿入法'''は、[[ソート]]の[[アルゴリズム]]の一つ。整列してある配列に追加要素を適切な場所に挿入すること。

[[計算複雑性|時間計算量]]は平均・最悪ケースでともに {{math|[[ランダウの記号|Ο]](''n''<sup>2</sup>)}} であり、[[クイックソート]]や[[マージソート]]などと比べれば遅い。しかし、
* アルゴリズムが単純で実装が容易
* 小さな配列に対しては高速
* [[安定ソート|安定]]
* [[in-placeアルゴリズム]]
* [[オンラインアルゴリズム]]
などの特徴から利用されることがある。

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

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

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

{|
|-
|| 8 || 4 || 3 || 7 || 6 || 5 || 2 || 1 ||（初期データ）
|-
| style="text-decoration:underline" | 4 || style="text-decoration:underline" | 8 || '''3''' || 7 || 6 || 5 || 2 || 1 ||（1回目のループ終了時）
|-
| style="text-decoration:underline" | 3 || style="text-decoration:underline" | 4 || style="text-decoration: underline" | 8 || '''7''' || 6 || 5 || 2 || 1 ||（2回目のループ終了時）
|-
| style="text-decoration:underline" | 3 || style="text-decoration:underline" | 4 || style="text-decoration:underline" | 7 || style="text-decoration:underline" | 8 || '''6''' || 5 || 2 || 1 ||（3回目のループ終了時）
|-
| style="text-decoration:underline" | 3 || style="text-decoration:underline" | 4 || style="text-decoration:underline" | 6 || style="text-decoration:underline" | 7 || style="text-decoration:underline" | 8 || '''5''' || 2 || 1 ||（4回目のループ終了時）
|-
| style="text-decoration:underline" | 3 || style="text-decoration:underline" | 4 || style="text-decoration:underline" | 5 || style="text-decoration:underline" | 6 || style="text-decoration:underline" | 7 || style="text-decoration:underline" | 8 || '''2''' || 1 ||（5回目のループ終了時）
|-
| style="text-decoration:underline" | 2 || style="text-decoration:underline" | 3 || style="text-decoration:underline" | 4 || style="text-decoration:underline" | 5 || style="text-decoration:underline" | 6 || style="text-decoration:underline" | 7 || style="text-decoration:underline" | 8 || '''1''' ||（6回目のループ終了時）
|-
| style="text-decoration:underline" | 1 || style="text-decoration:underline" | 2 || style="text-decoration:underline" | 3 || style="text-decoration:underline" | 4 || style="text-decoration:underline" | 5 || style="text-decoration:underline" | 6 || style="text-decoration:underline" | 7 || style="text-decoration:underline" | 8 ||（7回目のループ終了時。ソート完了）
|}

== 実装 ==
===C言語===
<syntaxhighlight lang="c">
void 
insertion_sort(int data[], size_t n) {
    for (size_t i = 1; i < n; i++) {
        if (data[i - 1] > data[i]) {
            size_t j = i;
            int tmp = data[i];
            do {
                data[j] = data[j - 1];
                j--;
            } while (j > 0 && data[j - 1] > tmp);
            data[j] = tmp;
        }
    }
}
</syntaxhighlight>

===Scheme===
<syntaxhighlight lang="scheme">
(define (insertion-sort ls)
  (define (insert x ls)
    (let loop ((ls ls) (acc '()))
      (if (null? ls)
          (append acc (cons x ls))
          (let ((y (car ls)))
            (if (< x y)
                (append (reverse acc) (cons x ls))
                (loop (cdr ls) (cons y acc)))))))
  (let loop ((ls ls) (acc '()))
    (if (null? ls)
        acc
        (let ((x (car ls)))
          (loop (cdr ls) (insert x acc))))))
</syntaxhighlight>

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

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

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

{{ソート}}
[[Category:ソート|そうにゆうそおと]]

[[no:Sorteringsalgoritme#Innstikksortering]]