アルゴリズムとプログラミング
シェルソートの特徴として最も正しいものはどれか。
ア.常にO(n log n)の計算量を保証する比較ソートである
イ.挿入ソートを改良したアルゴリズムで、間隔(gap)を徐々に縮めながら並べ替えを行う正解
ウ.ピボット要素を選んで配列を分割する分割統治法を用いる
エ.安定ソートであることが保証されている
解説
シェルソートは「まず遠距離引っ越しから始める引越し業者」みたいなもの。最初は遠い場所（大きいgap）の荷物を大ざっぱに整理して、だんだん近い荷物（小さいgap）を細かく整理する。最終的にgap=1になると普通の挿入ソートだが、すでに大体整理されているから高速！
なぜ イ が正解か
シェルソートの動作：①間隔(gap)を大きな値（例：配列サイズの半分）から始める②gap間隔で離れた要素どうしを挿入ソート③gapを縮小（例：半分に）して②を繰り返す④gap=1で通常の挿入ソートを実行→ほぼ整列済みなので高速。計算量はgapシーケンスに依存し、Knuthのgapでは約O(n^1.5)。挿入ソートの改良版という位置づけが本質。
出典: AI生成問題（学習用）