C#によるシェルソートの実装方法とサンプルコード解説

シェルソート（Shell Sort）は、配列の中で互いに離れた位置にある要素どうしを交換しながら整列を進め、その後ギャップ（間隔）を段階的に狭めていくソートアルゴリズムです。挿入ソート（Insertion Sort）を一般化した手法であり、最初に発表したドナルド・シェル（Donald Shell）にちなんでこの名前が付けられました。

以下に、C#でシェルソートを実装したサンプルプログラムを示します。

サンプルコード

using System;
namespace ShellSortDemo {
    public class Example {
        static void shellSort(int[] arr, int n) {
            int i, j, pos, temp;
            pos = 3;
            while (pos > 0) {
                for (i = 0; i < n; i++) {
                    j = i;
                    temp = arr[i];
                    while ((j >= pos) && (arr[j - pos] > temp)) {
                        arr[j] = arr[j - pos];
                        j = j - pos;
                    }
                    arr[j] = temp;
                }
                if (pos / 2 != 0)
                    pos = pos / 2;
                else if (pos == 1)
                    pos = 0;
                else
                    pos = 1;
            }
        }
        static void Main(string[] args) {
            int[] arr = new int[] { 56, 12, 99, 32, 1, 95, 25, 5, 100, 84 };
            int n = arr.Length;
            int i;
            Console.WriteLine("Shell Sort");
            Console.Write("Initial array is: ");
            for (i = 0; i < n; i++) {
                Console.Write(arr[i] + " ");
            }
            shellSort(arr, n);
            Console.Write("\nSorted Array is: ");
            for (i = 0; i < n; i++) {
                Console.Write(arr[i] + " ");
            }
        }
    }
}

実行結果

上記プログラムの実行結果は次のとおりです。

Shell Sort
Initial array is: 56 12 99 32 1 95 25 5 100 84
Sorted Array is: 1 5 12 25 32 56 84 95 99 100

プログラムの解説

まず、Main()メソッドの処理から見ていきましょう。ここでは初期状態の配列をコンソールに表示した後、shellSort()メソッドを呼び出して配列のソートを行っています。該当するコードは以下の部分です。

int[] arr = new int[] { 56, 12, 99, 32, 1, 95, 25, 5, 100, 84 };
int n = arr.Length;
int i;
Console.WriteLine("Shell Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
    Console.Write(arr[i] + " ");
}
shellSort(arr, n);

続いて、shellSort()メソッドでは、whileループとforループを組み合わせて配列をソートしています。この例では、シェルソートの初期ギャップとして3を設定しています。該当するコードは以下のとおりです。

static void shellSort(int[] arr, int n) {
    int i, j, pos, temp;
    pos = 3;
    while (pos > 0) {
        for (i = 0; i < n; i++) {
            j = i;
            temp = arr[i];
            while ((j >= pos) && (arr[j - pos] > temp)) {
                arr[j] = arr[j - pos];
                j = j - pos;
            }
            arr[j] = temp;
        }
        if (pos / 2 != 0)
            pos = pos / 2;
        else if (pos == 1)
            pos = 0;
        else
            pos = 1;
    }
}

このプログラムでは、初期ギャップを3とし、各パスが終わるごとにギャップを半分に減らしていきます（3 → 1）。最後のギャップ1の処理は通常の挿入ソートと同じ動作になりますが、その時点で配列はすでにかなり整列されているため、要素の移動回数が少なく済み、全体として効率よくソートが完了します。シェルソートの計算量はギャップ列の選び方に依存しますが、単純な挿入ソートと比べて実データに対して高い性能を発揮することで知られています。