シェルソートとは？

シェルソートの意味

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

シェルソートの具体例

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

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

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

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

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

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

• ヒープソートの説明として、適切なものはどれか。

  正解：未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。

  要点：ヒープソートは順序木の根から極値を取り出して整列する

  ヒープソートは、未整列部分をヒープ（親子間に大小関係が保たれた順序木）として構成し、根にある最小値または最大値を取り出して整列済み部分へ移す操作を繰り返す方式です。取り出すたびにヒープを再構成するため、計算量は要素数nに対しておおむね n log n となります。他の選択肢はシェルソート、クイックソート、バブルソートの説明です。

  出典：平成28年度 秋期 応用情報技術者試験 午前 問6（IPA）

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

  正解：2

  要点：シェルソートの間隔Hは3で割り続け、0になるまでの回数を数える

  データ数9なので手順(1)でH=[9÷3]=3となり、手順(2)で間隔3の部分列を整列する。1回目の手順(3)でH=[3÷3]=1、0でないので手順(2)に戻り間隔1で整列する。2回目の手順(3)でH=[1÷3]=0となり手順(4)で完了する。よって手順(3)の実行回数は2回である。

  出典：令和1年度 春期 応用情報技術者試験 午前 問6（IPA）