インサーションソートとは？
インサーションソートは、数列を昇順または降順に整列するためのアルゴリズムです。このアルゴリズムでは、配列の先頭から順番に要素を取り出し、配列の先頭からi番目までの要素を昇順または降順に整列した状態になるように、要素を適切な位置に挿入していきます。インサーションソートは、数列がある程度整列されている場合に高速に動作することが特徴です。
インサーションソートのアルゴリズム
インサーションソートのアルゴリズムは、以下のように記述されます。
- 配列Aを取得する
- 配列Aの先頭要素を基準値Vに設定する
- 配列Aの2番目の要素から順番に、基準値Vよりも小さい要素を探す
- 小さい要素が見つかった場合には、その要素を基準値Vの直前に挿入する
- 配列Aの先頭からi番目までの要素を整列する
- 配列Aのi+1番目の要素を基準値Vに設定する
- iが配列Aの末尾に達するまで、3-6の処理を繰り返す
インサーションソートの性能
インサーションソートの時間計算量はO(n^2)であり、安定ソートに分類されます。ただし、数列がある程度整列されている場合には、挿入操作がほとんど発生しないため、高速に動作することが期待できます。
一方で、数列がランダムに並んでいる場合や、逆順に並んでいる場合には、挿入操作が多発するため、処理時間が長くなる可能性があります。そのため、インサーションソートは、ボトムアップ型のメソッドとして、クイックソートやマージソートといった、トップダウン型のアルゴリズムと併用されることが一般的です。
以上のように、インサーションソートは、数列が整列されている場合に高速に動作するアルゴリズムであることがわかりました。実際にプログラムを記述して、その性能を確かめてみることをおすすめします。