挿入ソート 挿入ソートの概要

ウィキペディア

挿入ソート

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

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "挿入ソート" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2023年10月）

挿入ソート

クラス	ソート
データ構造	配列
最悪計算時間	${\displaystyle O(n^{2})}$
最良計算時間	${\displaystyle O(n)}$
平均計算時間	${\displaystyle O(n^{2})}$
最悪空間計算量	${\displaystyle O(n)}$ total, ${\displaystyle O(1)}$ auxiliary

時間計算量は平均・最悪ケースでともに Ο(n²) であり、クイックソートやマージソートなどと比べれば遅い。しかし、

• アルゴリズムが単純で実装が容易
• 小さな配列に対しては高速
• 安定
• in-placeアルゴリズム
• オンラインアルゴリズム

などの特徴から利用されることがある。

挿入ソートを高速化したソート法として、シェルソートが知られている。