シェルソートの対象試験と出題頻度

名前は知っているのに、動きを聞かれると手が止まる。

シェルソートは、そんな整列アルゴリズムの代表格ではないでしょうか。

シェルソートは、整列アルゴリズムの中で「挿入ソートの改良版」として位置づけられる手法。

FE・APどちらの科目A(午前)でも出題実績があり、頻出度はランクBです。ただし出題のされ方には強い偏りがあり、APでは繰返し回数の計算問題、FEでは説明文の識別として現れます。

なお科目B(午後)での出題は確認されていません。

出題情報を確認する
対象試験:
基本情報技術者(FE)/応用情報技術者(AP)
出題頻度:
★★★☆☆
ランクB(科目A・午前中心/科目Bでの出題は確認されていません)

シェルソートの定義

「挿入ソートの改良版」という説明を読んでも、間隔を空けるだけでなぜ速くなるのかが腹落ちしない。多くの受験者がここでつまずきます。

考案したのは1959年の Donald L. Shell。人名がそのまま手法名になっており、貝殻(shell)とは無関係です。

シェルソートとは、

「一定間隔おきの要素から成る部分列を整列し、間隔を詰めて繰り返す整列法」

です。

大部屋での座席替えを思い浮かべてみてください。

まず3列飛ばしのグループだけで大まかに背の順にし、大きな移動を先に済ませておく。すると最後に隣同士を見比べる段階では、入れ替えがほとんど発生しません。

📊 シェルソートの基本情報

項目 内容
英語名 Shell Sort(Shellsort)
考案者・年 Donald L. Shell(1959年)
位置づけ 挿入ソートの改良版(間隔Hを縮めながら適用)
平均計算量 O(n1.25)〜O(n1.5)程度(間隔列の選び方で変動)
最悪計算量 O(n2)
安定性 不安定(離れた要素を飛び越えて交換するため)

シェルソートの解説

なぜ「間隔を空ける」と速くなるのか

前提として挿入ソートの動きを確認しておきます。

未整列部分の先頭要素を取り出し、整列済み部分の中で正しい位置が見つかるまで、要素を1つずつ後ろへずらして差し込む手法。

この方式には弱点があり、列の末尾にある小さな値を先頭付近まで運ぶ場合、1マスずつしか移動できません。

シェルソートは、間隔Hだけ離れた要素同士を先に整列するという答えを出しました。

1回の移動でH個分を飛び越えられるため、大きな乱れが早い段階で解消されるわけです。次の表は AP 平成24年春 問7 と同じデータ列で、H=3のときの部分列を色分けしたもの。

📊 H=3のときの部分列分解(データ列 7,2,8,3,1,9,4,5,6)

添字 1 2 3 4 5 6 7 8 9
データ列 7 2 8 3 1 9 4 5 6
部分列 青 橙 緑 青 橙 緑 青 橙 緑
整列後 3 1 6 4 2 8 7 5 9

青(7,3,4)橙(2,1,5)緑(8,9,6)の3部分列を、それぞれ挿入法で整列した結果

H=3の段階を終えると、データ列は 3,1,6,4,2,8,7,5,9 まで整っています。

この後にH=1で仕上げる作業は、ほぼ整列済みの列をなでるだけ。

実務でも、前日分のソート済みデータへ当日分を数件マージするような処理は驚くほど多く、「遠い距離を先に詰めておく」というこの発想は、言語標準のソートがハイブリッド方式を採る理由の理解につながります。

間隔Hの縮め方と処理の流れ

試験問題では、処理が手順(1)〜(4)のループとして提示されます。

H=1のときが通常の挿入ソートに一致し、H=0になった時点が終了条件。

シェルソートにおけるHの更新サイクル

1
手順(1) Hの初期値を決める
H ← [9 ÷ 3]= 3
↓
2
手順(2) 部分列を挿入法で整列
H個おきに取り出した要素を整列。H=1のときが通常の挿入ソートと一致
↓
3
手順(3) 間隔を詰める
H ← [H ÷ 3] ※設問が数えるのはこの回数
↓
4
手順(4) 終了判定
H=0なら終了。0でなければ手順(2)へ戻る
↑ 手順(4)から手順(2)へループ(H=3 → 1 → 0 で2周)

[ ]は小数点以下切り捨て。数えるべき対象は手順(3)の実行回数です

擬似言語(科目B形式)での記述を見る
○shellSort(整数型の配列: data)
  整数型: n, h, i, j, tmp
  n ← data の要素数
  h ← n ÷ 3 の商
  while (h が 0 より大きい)
    for (i を h + 1 から n まで 1 ずつ増やす)
      tmp ← data[i]
      j ← i - h
      while (j が 1 以上 かつ data[j] が tmp より大きい)
        data[j + h] ← data[j]
        j ← j - h
      endwhile
      data[j + h] ← tmp
    endfor
    h ← h ÷ 3 の商
  endwhile

外側の while が間隔の縮小、内側が間隔Hを使った挿入処理に対応します。h を 1 に固定すれば挿入ソートそのもの。

他の整列アルゴリズムとの比較

手法の識別は「整列の単位が何か」で決まります。

隣接/部分列/分割グループ/木のどれを単位にしているかを、選択肢文から読み取ってください。

📊 主要な整列アルゴリズムとの比較

手法名 動作の核心(整列の単位) 平均計算量 最悪計算量 安定性
シェルソート 一定間隔おきの部分列を整列し、間隔を詰める O(n1.25)〜 O(n2) 不安定
挿入ソート 整列済み列の正しい位置に1要素ずつ差し込む O(n2) O(n2) 安定
クイックソート 基準値で大小2区分に分割し、各区分で同じ操作 O(n log n) O(n2) 不安定
ヒープソート 順序木から最大値(最小値)を順に取り出す O(n log n) O(n log n) 不安定
バブルソート 隣り合う要素を比較し、順序が逆なら交換 O(n2) O(n2) 安定

5手法はいずれも配列内で並べ替える方式で、作業用の追加メモリはほとんど不要です

平均計算量の O(n1.25) という値は、間隔列(ギャップ列)の選び方によって変わります。

オーダー記法の読み方を確認する程度でよく、暗記の優先度は低い。

押さえるべきは、最悪ケースでは O(n2) まで劣化しうる、つまりクイックソートと同じ弱点を抱えているという一点です。

📝 ポイント整理

・間隔Hだけ離れた要素を先に整列するため、遠くの要素を一気に動かせる
・H=1の段階は通常の挿入ソートと一致し、H=0が終了条件
・高速側に分類されるが、最悪計算量はO(n2)まで劣化しうる不安定なソート

シェルソートは試験ではこう出る!

出題パターン分析

シェルソートの出題は3つの型に分かれます。自分が正解になる回より、他のソートを問う設問でダミー選択肢として登場する回のほうが圧倒的に多い点が特徴。

📝 IPA試験での出題パターン

パターン1:Hの更新回数を数える計算問題
AP 平成24年春 問7、AP 平成31年春 問6。シェルソートが単独で主役になる唯一の形式で、同一構成の問題が旧試験時代から繰り返し流用されています。

 

パターン2:他ソートの説明問題における正しいダミー
AP 令和3年秋 問5、AP 平成26年秋 問6。「ある間隔おきに…間隔が1になるまで」の定型句をシェルソートと即断できれば、残り3択に絞れます。

 

パターン3:用語と説明を入れ替える誤記述型
FE 平成20年春 問13。シェルソートの名前に別手法の動作を接続して誤りを作る形式で、名前と定型句をペアで覚えていないと引っかかります。

 

FEはパターン2・3、APはこれに加えてパターン1への備えが必要です。

📊 選択肢を切るためのキーワード判定

一定間隔おきの部分列
→ シェルソート
基準値で2区分に分割
→ クイックソート
順序木から取り出す
→ ヒープソート

「隣り合う要素の交換」はバブルソート。4語をこの形で覆えば選択肢問題は落としません

ひっかけポイントと対策

誤答の型は決まっています。バブルソートの説明をシェルソートの名前に付け替える形が最頻出。

⚠️ ひっかけ早見表

誤答の値・選択肢 その正体
シェルソートは隣り合う要素を交換 バブルソートの説明(FE H20春 問13型)
クイックソートは一定間隔の部分列を整列 シェルソートの定型句の付替え
手順(3)の回数を3回と答える 3・1・0というHの値の個数を数えた誤り
部分列を整列した回数を答える 手順(2)の回数。設問は手順(3)を問う

📝 試験区分別の対策方針

・FE:説明文の識別に絞り、定型句の暗記を最優先
・AP:加えて手順(3)の回数計算を紙でトレースしておく
・共通:手法名と動作の定型句を必ずペアで記憶する

シェルソートの出題実績一覧を見る(7件)

AP 平成24年春 問7:手順(1)〜(4)を示し、データ列 7,2,8,3,1,9,4,5,6 の整列で手順(3)を何回繰り返すかを問う(正解ア=2回/主役・計算問題)

AP 平成31年春 問6:上記と同一構成の流用問題(正解ア=2回/主役・計算問題)

AP 令和3年秋 問5:バブルソートの説明を選ぶ問題(正解ウ/選択肢アがシェルソートの説明=ダミー)

AP 平成26年秋 問6:データ列が上から下に推移する整列方法を選ぶ問題(正解エ=マージソート/選択肢イがシェルソート)

FE 平成20年春 問13:整列方法に関する記述として適切なものを選ぶ問題(正解エ=ヒープソート/シェルソートの名前にバブルソートの説明を接続した誤記述型)

SW 平成16年春 問11:AP 平成24年春 問7 の初出(旧・ソフトウェア開発技術者/正解ア)

SW 平成19年秋 問10:同問題の再出題(旧試験/正解ア)

【AP頻出】「手順(3)を何回繰り返すか」問題を3ステップで解く

AP 平成24年春 問7 と平成31年春 問6 は、設問文まで含めてほぼ同じ問題。データ数9の列を、前掲の手順(1)〜(4)で整列するとき手順(3)を何回繰り返すかが問われました。次の3ステップで確定できます。

ステップ1:Hの初期値を出す。

 手順(1)は H ← [データ数 ÷ 3]なので、9 ÷ 3 でH=3。


ステップ2:Hが0になるまでの更新列を書き出す。

 3 → 1 → 0 の3つが並びます([3÷3]=1、[1÷3]=0)。


ステップ3:更新の矢印の本数を数える。

 3から1、1から0の2本。よって手順(3)の実行回数は2回で、正解はアです。

📊 Hの値とデータ列の遷移表(手順(3)のカウンタ付き)

Hの値 部分列の個数 手順(2)実行後のデータ列 手順(3)の実行回数
H=3 3個 3, 1, 6, 4, 2, 8, 7, 5, 9 1回目(H←1)
H=1 1個(通常の挿入ソート) 1, 2, 3, 4, 5, 6, 7, 8, 9 2回目(H←0)
H=0 — 手順(4)の判定で終了 合計 2回

カウンタが増える行数を数えれば、手順(3)の回数がそのまま求まります

この設問には落とし穴があります。

部分列を整列した回数(手順(2)=2回)と、Hを更新した回数(手順(3)=2回)が偶然一致するため、どちらを数えたのか自分でも区別がつかなくなる。

筆者もAP午前の演習で、手順(2)の回数を答えて外した経験があります。

手順に番号が振られた問題では、問題文の番号に指を置いたまま数える。この癖をつけておけば取りこぼしません。

【確認テスト】シェルソートの理解度チェック

Q. シェルソートの説明として、最も適切なものはどれでしょうか?

  • A. 隣り合う要素を比較して、大小の順が逆であればそれらの要素を入れ替えるという操作を繰り返す。
  • B. ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて同様の操作を行い、間隔が1になるまでこれを繰り返す。
  • C. 中間的な基準値を決めて、それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分け、それぞれの区分で同様の操作を繰り返す。
正解と解説を見る

正解:B

解説:
「ある間隔おきに取り出した要素から成る部分列」と「間隔が1になるまで繰り返す」は、IPAがシェルソートを表すときに用いる定型句です。この2語がそろえば即断できます。間隔が1になった段階の処理は通常の挿入ソートと同一で、そこまでに大きな乱れが解消されているため、最後の仕上げはごくわずかな入れ替えで完了します。

Aが不正解の理由:「隣り合う要素の交換」はバブルソートのキーワードです。この記述をシェルソートの名前に接続する誤記述型が、FE 平成20年春 問13 でも実際に出題されました。

Cが不正解の理由:「中間的な基準値による2区分への振り分け」はクイックソートの説明です。基準値で分割して同じ操作を再帰的に繰り返す点が識別キーになります。

シェルソートの関連用語ネットワーク

シェルソートは単独で覚えるより、整列アルゴリズム全体の中での位置を押さえたほうが定着します。

📊 関連用語マップ

カテゴリ 関連用語
前提知識 アルゴリズム/データ構造(配列・リスト)
関連用語 挿入ソート(本記事内で解説/個別記事は準備中)/バブルソート/クイックソート/ヒープソート
発展 オーダー記法/2分探索法(整列済みデータを前提とする探索)