基本挿入法とも呼ばれる挿入ソートは、シンプルで実装が容易であり、最も安定しているソートアルゴリズムである。数値が正しい場所にない場合に、その数値を正しい位置に挿入する。平均、最悪計算量は共にO(n^2)である。
挿入ソートを高速化したものとしてシェルソートがある。
- 0番目の要素と1番目の要素を比較する。
- 0番目の要素が1番目の要素より大きい場合、要素を入れ替える。
- 2番目の要素と1つ前の要素を比較する。
- 2番目の要素が1つ前の要素より大きい場合、要素を入れ替える。
- 2番目の要素が正しい位置に来るまで2.と4.を実行する。
- ソートが完了するまで3.から5.を何度も繰り返す。
初期配列 1 4 3 9 5
ソート後配列 1 3 4 5 9
ステップ 1回目
- ( 1 4 3 9 5 ) → ( 1 4 3 9 5 ), ここでアルゴリズムは最初の２つの要素を比較し、順番通りのため(4 > 1), アルゴリズムは入れ替えをしない。
2回目
- ( 1 4 3 9 5 ) → ( 1 3 4 9 5 ), 4 > 3なので入れ替える。
- ( 1 3 4 9 5 ) → ( 1 3 4 9 5 )
ここで選択した要素が1つ前の要素よりも大きいため、アルゴリズムは選択した要素の次の要素に移る。(この配列の場合は3の次である4)
3回目
- ( 1 3 4 9 5 ) → ( 1 3 4 9 5 )
4回目
- ( 1 3 4 9 5 ) → ( 1 3 4 9 5 )
5回目
- ( 1 3 4 9 5 ) → ( 1 3 4 5 9 )
- ( 1 3 4 5 9) → ( 1 3 4 5 9 )
さて、この時点で配列はすでにソートされたが、まだ配列の最後の要素にたどり着いていない。アルゴリズムは配列の最後の要素を選択するまで続く。
6回目
- ( 1 3 4 5 9 ) → ( 1 3 4 5 9 )