二分挿入ソートとは？
二分挿入ソートとは、挿入していく整列で、挿入位置を先頭から順に比べて探すのではなく、既に整列済みの前半部分に対して二分探索で決める方法。比較回数を減らせるが、決めた位置へ入れるための要素の移動回数は減らない。
にぶんそうにゅうそーと
二分挿入ソートの意味
挿入していく整列で、挿入位置を先頭から順に比べて探すのではなく、既に整列済みの前半部分に対して二分探索で決める方法。比較回数を減らせるが、決めた位置へ入れるための要素の移動回数は減らない。
二分挿入ソートの具体例
前半5要素が整列済みのとき、6番目の要素の入る場所を、中央と比べて範囲を半分ずつ絞りながら3回程度の比較で特定する。位置が決まったら、そこから後ろの要素を1つずつずらして空きを作り、値を書き込む。
二分挿入ソートは試験でどう引っ掛けられる？
比較が減るからといって全体の計算量が改善するわけではない。移動が支配的なため、全体では要素数の2乗に比例したままである。比較のコストが高い場合にだけ効く、という条件付きの改良である点が要点。
二分挿入ソートと関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。