Instance Name Help

挿入ソート

挿入ソート（Insertion Sort）は、 単純なソートアルゴリズムの一つです。

アルゴリズムの仕組み

挿入ソートは、配列の要素をソートされた部分と未ソートの部分に分けて考えます。未ソートの部分から要素を一つずつ取り出し、ソートされた部分の適切な位置に挿入することで、ソートを行います。

具体的な手順

  1. 配列の2番目の要素から始めます。

  2. 現在の要素を、 それより前のソート済み部分と比較します。

  3. 現在の要素よりも大きい要素を右にシフトして、挿入する場所を空けます。

  4. 現在の要素を空いた場所に挿入します。

  5. このプロセスを配列の最後まで繰り返します。

図による説明

配列 [1-5] を挿入ソートでソートする過程を図で示します。

Step

Array

Key

Comparison

Action

1

[1-5]

1

1 < 5

Shift 5 to the right, insert 1

2

[1-5]

4

4 < 5

Shift 5 to the right, insert 4

3

[1-5]

2

2 < 5, 2 < 4, 2 < 1は偽

Shift 5と4 to the right, insert 2

4

[1-5]

8

8 < 5, 8 < 4, 8 < 2は偽

No shift needed

5

[1-5]

Array is sorted

表による時間計算量の比較

ケース

時間計算量

最良の場合

O(n)

平均的な場合

O(n^2)

最悪の場合

O(n^2)

特徴

  • 実装が簡単

  • 小さなデータセットに対しては効率的

  • 安定なソート (同じ値の要素の順序が保持されます)

  • 追加のメモリをほとんど必要としません (インプレースソート)

ソース内の関連情報

ソースには、挿入ソートのような単純なソート方法は、 最悪の場合にO(n^2)の計算量が必要であると記載されています。

Last modified: 06 February 2025
ハッシュ法（Hashing）の説明マージソート