insertion sort

デジタル大辞泉

インサーション‐ソート【insertion sort】

読み方：いんさーしょんそーと

⇒挿入ソート

そうにゅう‐ソート〔サフニフ‐〕【挿入ソート】

読み方：そうにゅうそーと

《insertion sort》コンピューターでデータをある基準によって並べかえるソートのうち、最も基本的なアルゴリズムの一。データの要素を最初から順番に二つずつ取り出して比較し、整列させていく。要素が逆に並んでいる場合、非常に時間がかかるという欠点がある。インサーションソート。基本挿入法。→シェルソート →選択ソート

IT用語辞典バイナリ

挿入ソート

読み方：そうにゅうソート
別名：インサーションソート，基本挿入法
【英】insertion sort

挿入ソートとは、データを大きい順、小さな順など一定の規則で並べ替えるソート（整列）の方法の1つである。

挿入ソートでは、ソートが済んでいるデータと新しいデータを比較して挿入する位置を決めることを繰り返すアルゴリズムが用いられる。最初は2つのデータを比較することでソートが始まる。3番目のデータはそのソート済み2個のデータと比較し、挿入する位置を決める。以下同様の作業を繰り返す。

ソート手法には多くの方法があり、それぞれ一長一短があるため、ソートの対象となるデータの特長、件数などにより、採用するアルゴリズムを適切に選ぶ必要がある。挿入ソートは、データの並びによっては他の方法に比べて非効率的となる場合がある。逆にデータの件数がそれほど多くなく、高速だが複雑なアルゴリズムによるプログラムを作成するまでもないような場合には、挿入ソートは適した方法であるといえる。

なお、同じデータの順番がソート前後によって変化しないソート手法を「安定なソート」と言うが、挿入ソートは安定なソートである。

情報処理のほかの用語一覧

アルゴリズム：

巡回セールスマン問題  昇順  シーケンシャルサーチ  挿入ソート  ソート  スタック  2分木

>>アルゴリズムカテゴリの他の用語

ウィキペディア

挿入ソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/10/25 00:33 UTC 版)

挿入ソート

クラス	ソート
データ構造	配列
最悪計算時間	$O(n^{2})$ カテゴリ