インサーション‐ソート【insertion sort】
読み方:いんさーしょんそーと
挿入ソート
別名:インサーションソート,基本挿入法
【英】insertion sort
挿入ソートとは、データを大きい順、小さな順など一定の規則で並べ替えるソート(整列)の方法の1つである。
挿入ソートでは、ソートが済んでいるデータと新しいデータを比較して挿入する位置を決めることを繰り返すアルゴリズムが用いられる。最初は2つのデータを比較することでソートが始まる。3番目のデータはそのソート済み2個のデータと比較し、挿入する位置を決める。以下同様の作業を繰り返す。
ソート手法には多くの方法があり、それぞれ一長一短があるため、ソートの対象となるデータの特長、件数などにより、採用するアルゴリズムを適切に選ぶ必要がある。挿入ソートは、データの並びによっては他の方法に比べて非効率的となる場合がある。逆にデータの件数がそれほど多くなく、高速だが複雑なアルゴリズムによるプログラムを作成するまでもないような場合には、挿入ソートは適した方法であるといえる。
なお、同じデータの順番がソート前後によって変化しないソート手法を「安定なソート」と言うが、挿入ソートは安定なソートである。
アルゴリズム: | 巡回セールスマン問題 昇順 シーケンシャルサーチ 挿入ソート ソート スタック 2分木 |
挿入ソート
(インサーション‐ソート から転送)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/10/25 00:33 UTC 版)
挿入ソート(そうにゅうソート、英: insertion sort)あるいは基本挿入法は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。
- 1 挿入ソートとは
- 2 挿入ソートの概要
- 3 アルゴリズム
- 4 二分挿入ソート
- インサーション‐ソートのページへのリンク