シェルソートとは？

シェルソートの意味

一定間隔だけ離れた要素どうしを挿入ソートで整列し、その間隔を徐々に狭めて最後に間隔1で仕上げる方法。挿入ソートの改良版で、遠く離れた要素を早い段階で大きく移動させられるため、平均的な計算量がO(n²)より小さくなる点がFEで問われる。

シェルソートの具体例

8要素の配列なら間隔4で1番目と5番目、2番目と6番目…を比較・整列し、次に間隔2、最後に間隔1で挿入ソートを行う。最後の段階に到達したときにはデータがほぼ整列済みなので、挿入ソートが得意な状態になり全体として高速になる。

シェルソートは試験でどう引っ掛けられる？

間隔を狭める順序（大きい間隔から小さい間隔へ）が逆に書かれた選択肢が出る。また最後は必ず間隔1で走らせる必要があり、これを省くと整列が完了しない。離れた要素を交換するため不安定なソートである。

シェルソートと関連する用語

• 整列アルゴリズム（バブルソート・選択ソート・挿入ソート）
• クイックソート・マージソート・ヒープソート
• 安定ソート

シェルソートが出た過去問

• 次の手順はシェルソートによる整列を示している。データ列 7, 2, 8, 3, 1, 9, 4, 5, 6 を手順(1)〜(4)に従って整列するとき、手順(3)…

  正解：2

  要点：シェルソートの間隔Hは3分の1ずつ縮み、9件なら3→1→0

  データ数は9なので、まずH=[9÷3]=3で手順(2)を実行する。次に手順(3)でH=[3÷3]=1となり、Hは0でないので手順(2)へ戻って整列する。再び手順(3)でH=[1÷3]=0となり、手順(4)で完了する。したがって手順(3)を実行した回数は2回である。

  出典：令和1年度 春期 高度共通_午前I試験 am1 問3（IPA）