シェルソート実装・詳しい計算量解説

2026/04/29

Cover Image for シェルソート実装・詳しい計算量解説

シェルソート(Shell Sort)

このサイトでのシェルソートの定義は以下の通りです。¹

計算量 $O(N^2)$ (gap 列の選び方によりさらに改善できる)

シェルソートは 1959 年に Donald Shell によって考案されたアルゴリズムで、考案者の名前にちなんで「シェルソート」と呼ばれます。

シェルソートのアルゴリズム

シェルソートは挿入ソートの改良版です。

挿入ソートの詳しい解説はこちらを参照してください。

挿入ソートは「データがほぼ整列している」場合は非常に高速ですが、「遠くに離れた要素同士の入れ替え」は隣接要素の交換を何度も繰り返す必要があり遅いという欠点があります。

シェルソートはこの欠点を、最初は離れた要素同士、徐々に近い要素同士を比較していくという発想で克服します。

詳しく手順を説明すると以下の通りです。

ある間隔 $gap$ を決める(例: $N/2$ )
配列を $gap$ 飛ばしで取り出した部分列ごとに挿入ソートを行う
$gap$ を縮める(例: $gap \leftarrow gap / 2$ )
$gap = 1$ になるまで 2〜3 を繰り返す
最後に $gap = 1$ で挿入ソートを行うと、配列全体が整列する

$gap$ が大きいときは要素を大きく移動でき、 $gap$ が小さいときには配列がほぼ整列されているので挿入ソートが高速に動作します。

shell_sort

gap の選び方

シェルソートの性能は gap 列の選び方によって大きく変わります。代表的な gap 列を紹介します。

提案者	gap 列	最悪計算量
Shell (1959)	$N/2, N/4, \ldots, 1$	$O(N^2)$
Hibbard (1963)	$2^k - 1$	$O(N^{3/2})$
Knuth (1973)	$\frac{3^k - 1}{2}$	$O(N^{3/2})$
Sedgewick (1986)	複合列	$O(N^{4/3})$

本記事では最もシンプルな Shell の元々の gap 列 $N/2, N/4, \ldots, 1$ で実装を示します。

実装例

以下に C 言語での実装例を示します。

#include <stdio.h>
 
void shellSort(int *data, int n)
{
    for (int gap = n / 2; gap > 0; gap /= 2)
    {
        for (int i = gap; i < n; i++)
        {
            int tmp = data[i];
            int j = i;
            while (j >= gap && data[j - gap] > tmp)
            {
                data[j] = data[j - gap];
                j -= gap;
            }
            data[j] = tmp;
        }
    }
}

外側のループで $gap$ を縮め、内側で「 $gap$ 飛ばしの挿入ソート」を実行しています。

シェルソートの計算量

シェルソートの厳密な計算量解析は gap 列の選び方に強く依存し、未解決の部分が多い難しい問題です。

ここでは Shell の元の gap 列 $N/2, N/4, \ldots, 1$ を用いた場合の最悪計算量について議論します。

各 gap での計算量

ある gap $g$ に対する処理を考えます。

このとき配列は $g$ 個の独立な部分列に分割され、それぞれの長さは約 $N/g$ です。

各部分列に対する挿入ソートの最悪計算量は、長さ $m$ の挿入ソートが $O(m^2)$ なので $O((N/g)^2)$ です。

部分列が $g$ 個あるので、gap $g$ 1 回分の計算量は

g \times O\left(\left(\frac{N}{g}\right)^2\right) = O\left(\frac{N^2}{g}\right)

となります。

全体の計算量

gap が $N/2, N/4, \ldots, 1$ と縮んでいくときの全体の計算量は、各 gap での計算量の和となります。

\sum_{k=0}^{\log_2 N - 1} O\left(\frac{N^2}{N / 2^{k+1}}\right) = \sum_{k=0}^{\log_2 N - 1} O\left(2^{k+1} N\right)

= O(N) \sum_{k=0}^{\log_2 N - 1} 2^{k+1}

ここで等比数列の和

\sum_{k=0}^{\log_2 N - 1} 2^{k+1} = 2 \cdot (2^{\log_2 N} - 1) = 2N - 2

を用いると、全体の計算量は

O(N) \times O(N) = O(N^2)

となります。

したがって、Shell の元の gap 列を用いた場合のシェルソートの最悪計算量は $O(N^2)$ です。

gap 列の改善による高速化

上記の見積もりは緩めですが、実際にはシェルソートは挿入ソートよりかなり高速に動きます。

これは「 $gap$ が小さくなるころには配列がほぼ整列されており、内側の挿入ソートが線形時間に近づく」ためです。

さらに、Hibbard 列や Sedgewick 列のような工夫された gap 列を用いると、最悪計算量を $O(N^{3/2})$ や $O(N^{4/3})$ まで改善できることが知られています。

シェルソートの特徴

インプレースソート: 追加のメモリをほとんど必要としない
安定ソートではない: 離れた位置の要素を交換するため、同じ値の要素の相対順序が保たれない
実装が比較的シンプル: クイックソートやヒープソートに比べて短く書ける
小〜中規模データに強い: 数千要素程度までは $O(N \log N)$ アルゴリズムに迫る性能を出すことがある

シェルソートは「単純さの割に速い」という特徴から、組み込み環境や教育目的でも採用されることがあります。

以上がシェルソートの基本的な解説と C 言語での実装、および計算量の議論でした。

関連記事

ソートアルゴリズムを一覧で比較したい方はソートアルゴリズム比較・計算量まとめをご覧ください。

それぞれのソートアルゴリズムの定義は、他のサイトや書籍等での定義と少々異なる場合があります。 ↩

おすすめ記事

Cover Image for 挿入ソート実装・詳しい計算量解説

挿入ソート実装・詳しい計算量解説

挿入ソート(Insertion Sort)の説明、C言語での実装、数式を用いた計算量の議論を解説します挿入ソートはデータ配列のはじめから終わりまで、ソート済みの部分と未ソートの部分に分け、未ソートの部分から一つずつ取り出して、ソート済みの部分に挿入していくアルゴリズムです。計算量はO(N^2)です。

Cover Image for 【データ構造】キューとスタックの基本解説

【データ構造】キューとスタックの基本解説

キューとスタックのデータ構造について、その違いや用途、Pythonでの実装例を用いて解説します。キューは「先入れ先出し (FIFO: First-In-First-Out)」のデータ構造です。スタックは「後入れ先出し (LIFO: Last-In-First-Out)」のデータ構造です。

Cover Image for ソートアルゴリズム比較・計算量まとめ｜安定性・特徴一覧

ソートアルゴリズム比較・計算量まとめ｜安定性・特徴一覧

主要なソートアルゴリズム(バブル・選択・挿入・シェーカー・シェル・マージ・クイック・ヒープ)の計算量、安定性、メモリ使用量、特徴を一覧で比較します。用途に応じた使い分け方や、それぞれの詳しい解説記事へのリンクもまとめました。