シェルソートとは？しぇるそーと
シェルソートとは、一定間隔だけ離れた要素どうしを挿入ソートで整列し、その間隔を段階的に狭めて最後に間隔1で仕上げる整列法。遠く離れた要素を早い段階で大きく動かせるため、単純な挿入ソートよりも平均計算量が小さくなる。間隔の選び方によって計算量が変わる点が特徴である。
最終更新：2026-10-06
この語が出る過去問を解く →背景
挿入ソートはほぼ整列済みのデータに対しては極めて速いが、小さい値が末尾にあると1つずつしか前へ動かせず交換回数が跳ね上がる。この「隣としか交換できない」制約が遅さの正体である。先に粗い間隔で大まかに整えてから間隔を詰めれば、最後の仕上げを挿入ソートの得意な状態から始められる。
具体例
8要素なら間隔4で1番目と5番目、2番目と6番目…を整列し、次に間隔2、最後に間隔1で挿入ソートを行う。最後の段階に入る時点でほぼ整列済みなので交換がほとんど起きない。Knuthが示した1,4,13,40…の系列が、間隔の実用的な選び方として知られる。
試験での引っ掛け
間隔を狭める向き（大きい間隔から小さい間隔へ）を逆にした選択肢が出る。最後は必ず間隔1で走らせないと整列は完了しない。離れた要素どうしを交換するため不安定なソートであり、安定なマージソートや挿入ソートとの対比で問われる。
関連用語
出た過去問
問題文で直接問われたものと、解説の中で触れられたものが含まれます。
出典：平成28年度 秋期 応用情報技術者試験 午前 問6（IPA）解説で登場
ヒープソートの説明として、適切なものはどれか。
正解：未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。
要点：ヒープソートは順序木の根から極値を取り出して整列する
ヒープソートは、未整列部分をヒープ（親子間に大小関係が保たれた順序木）として構成し、根にある最小値または最大値を取り出して整列済み部分へ移す操作を繰り返す方式です。取り出すたびにヒープを再構成するため、計算量は要素数nに対しておおむね n log n となります。他の選択肢はシェルソート、クイックソート、バブルソートの説明です。
出典：平成31年度 春期 応用情報技術者試験 午前 問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 基礎理論 ＞ 2. アルゴリズム ＞ (2) 代表的なアルゴリズムに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。