シェルソート

デジタル大辞泉

シェル‐ソート【shell sort】

読み方：しぇるそーと

コンピューターでデータをある基準によって並べかえるソートで使われるアルゴリズムの一。挿入ソートを改良し、隣り合った要素だけを比較するのではなく、ある適当な間隔で取り出した要素列に対し、挿入ソートを行い、徐々にその間隔を詰めて同じ走査を繰り返す。

IT用語辞典バイナリ

シェルソート

【英】shell sort

シェルソートとは、ソート（整列）のアルゴリズムの一種で、挿入ソートを改良したアルゴリズムのことである。アメリカのコンピュータ科学者ドナルド・シェル（Donald Shell）によって考案された。

シェルソートの原型となっている挿入ソートは、もっとも単純なアルゴリズムの一つで、原理上ランダムな並びのデータを整列させるには効率が悪いという欠点がある。シェルソートでは、初めに大きなデータと小さなデータとを大まかに分け、その後に挿入ソートを行う、という手順を踏むことで、挿入ソートの効率化を図ろうとするものである。

シェルソートでは、まず一定間隔の全てのデータの組み合わせに対して小さなデータが前にくるよう交換処理を行う。これを、間隔を小さくしながら隣同士の交換になるまで同じことを繰り返し、最後には挿入ソートを行う。

なお、同じデータの順番がソート前後によって変化しないソート手法を「安定なソート」と言うが、挿入ソートとは違い、シェルソートは安定なソートではない。

情報処理のほかの用語一覧

アルゴリズム：

整列  セレクションソート  選択ソート  シェルソート  識別子  巡回セールスマン問題  昇順

>>アルゴリズムカテゴリの他の用語

ウィキペディア

シェルソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2026/04/03 13:40 UTC 版)

シェルソート

間隔 23, 10, 4, 1 でのシェルソートの実行
クラス	ソート
データ構造	配列
最悪計算時間	間隔に依存
最良計算時間	$\mathrm {O} (n\log n)$ 間隔5, 3, 1のシェルソートにおける要素の交換を示した図 シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、1959年にドナルド・シェルが開発したソートのアルゴリズム。挿入ソートの一般化であり、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムである。ただし、挿入ソートと異なり、安定ソートではなくなる。 アルゴリズム アルゴリズムの基本は挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という長所を持つが、隣接した要素同士しか比較・交換を行わないため、あまり整列されていないデータに対しては低速であった。 シェルソートは、「飛び飛びの列を繰り返しソートして、配列を大まかに整列された状態に近づけていく」ことにより、挿入ソートの長所を活かしたものである。 アルゴリズムの概略は次のとおりである。 適当な間隔 $h$ カテゴリ