挿入ソート¶
挿入ソート（insertion sort）は単純なソートアルゴリズムであり、その動作原理は手作業でトランプの山を整える過程と非常によく似ています。
具体的には、未ソート区間から基準要素を 1 つ選び、その要素を左側の整列済み区間の要素と 1 つずつ比較し、正しい位置に挿入します。
以下の図は、配列に要素を挿入する操作の流れを示しています。基準要素を base とすると、目的のインデックスから base までのすべての要素を 1 つずつ右に移動し、その後 base を目的のインデックスに代入する必要があります。
アルゴリズムの流れ¶
挿入ソート全体の流れを以下の図に示します。
- 初期状態では、配列の 1 番目の要素はすでに整列済みです。
- 配列の 2 番目の要素を
baseとして選び、正しい位置に挿入すると、**配列の先頭 2 要素が整列済み**になります。 - 3 番目の要素を
baseとして選び、正しい位置に挿入すると、**配列の先頭 3 要素が整列済み**になります。 - このように繰り返し、最後のラウンドで最後の要素を
baseとして選んで正しい位置に挿入すると、**すべての要素が整列済み**になります。
コード例は以下のとおりです。
アルゴリズムの特徴¶
- 計算量は \(O(n^2)\)、適応的ソート：最悪の場合、各挿入操作ではそれぞれ \(n - 1\)、\(n-2\)、\(\dots\)、\(2\)、\(1\) 回のループが必要であり、合計は \((n - 1) n / 2\) となるため、時間計算量は \(O(n^2)\) です。データが整列済みであれば、挿入操作は早期に終了します。入力配列が完全に整列済みである場合、挿入ソートは最良の時間計算量 \(O(n)\) に達します。
- 空間計算量は \(O(1)\)、インプレースソート：ポインタ \(i\) と \(j\) は定数サイズの追加領域しか使用しません。
- 安定ソート：挿入操作の過程では、要素を等しい要素の右側に挿入するため、それらの順序は変化しません。
挿入ソートの利点¶
挿入ソートの時間計算量は \(O(n^2)\) であり、これから学ぶクイックソートの時間計算量は \(O(n \log n)\) です。挿入ソートの時間計算量のほうが大きいにもかかわらず、**データ量が小さい場合には、挿入ソートのほうが通常は高速**です。
この結論は、線形探索と二分探索の適用条件に関する結論と似ています。クイックソートのような \(O(n \log n)\) のアルゴリズムは分割統治法に基づくソートアルゴリズムであり、一般により多くの基本演算を含みます。一方、データ量が小さい場合は、\(n^2\) と \(n \log n\) の値は比較的近く、計算量が支配的ではなくなり、各ラウンドにおける基本演算の回数が決定的な役割を果たします。
実際、多くのプログラミング言語（たとえば Java）の組み込みソート関数では挿入ソートが採用されており、その大まかな考え方は次のとおりです。長い配列にはクイックソートなどの分割統治法に基づくソートアルゴリズムを使い、短い配列には直接挿入ソートを使います。
バブルソート、選択ソート、挿入ソートはいずれも時間計算量が \(O(n^2)\) ですが、実際には、挿入ソートはバブルソートや選択ソートよりもはるかに高い頻度で使われます。主な理由は次のとおりです。
- バブルソートは要素の交換によって実装され、1 つの一時変数を必要とするため、合計で 3 回の基本演算が関わります。これに対して、挿入ソートは要素の代入に基づいており、必要な基本演算は 1 回だけです。したがって、バブルソートの計算コストは通常、挿入ソートより高くなります。
- 選択ソートの時間計算量はどのような場合でも \(O(n^2)\) です。**部分的に整列されたデータが与えられた場合、挿入ソートは通常、選択ソートより効率的**です。
- 選択ソートは安定ではないため、多段ソートには適用できません。