挿入ソート

挿入ソートでは、ソートが済んでいるデータと新しいデータを比較して挿入する位置を決めることを繰り返すアルゴリズムが用いられる。 最初は2つのデータを比較することでソートが始まる。 3番目のデータはそのソート済み2個のデータと比較し、挿入する位置を決める。 以下同様の作業を繰り返す。 ソート手法には多くの方法があり、それぞれ一長一短があるため、ソートの対象となるデータの特長、件数などにより、採用するアルゴリズムを適切に選ぶ必要がある。 挿入ソートは、データの並びによっては他の方法に比べて非効率的となる場合がある。 逆にデータの件数がそれほど多くなく、高速だが複雑なアルゴリズムによるプログラムを作成するまでもないような場合には、挿入ソートは適した方法であるといえる。 なお、同じデータの順番がソート前後によって変化しないソート手法を「安定なソート」と言うが、挿入ソートは安定なソートである。