Javaで学ぶコムソート（Comb Sort）の実装方法とサンプルコード

コムソートとは

コムソート（Comb Sort）は、バブルソートを改良したソートアルゴリズムです。リストの後方に残りやすい小さな値（通称「ウミガメ」と呼ばれる要素）を効率的に手前に移動させ、転倒（順序が逆になっているペア）を一つずつ解消していきます。

バブルソートとの最大の違いは、隣接する要素だけでなく、一定の間隔（ギャップ）を空けた要素同士を比較する点です。このギャップを毎回約1.3倍の比率で縮小していくことで、ソートの効率が大幅に向上します。

Javaによる実装例

それでは、実際のコードを見てみましょう。

import java.util.Arrays;
public class Demo{
    void comb_sort(int nums[]){
        int len_gap = nums.length;
        float shrink_val = 1.3f;
        boolean swap = false;
        while (len_gap > 1 || swap) {
            if (len_gap > 1) {
                len_gap = (int)(len_gap / shrink_val);
            }
            swap = false;
            for (int i = 0; len_gap + i < nums.length; i++){
                if (nums[i] > nums[i + len_gap]) {
                    swap(nums, i, i + len_gap);
                    swap = true;
                }
            }
        }
    }
    private static void swap(int nums[], int x, int y) {
        Integer temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
    public static void main(String args[]){
        Demo ob = new Demo();
        int nums[] = {6, 78, 90, -12, -45, 0, -1, 45};
        System.out.println("The original array contains ");
        System.out.println(Arrays.toString(nums));
        ob.comb_sort(nums);
        System.out.println("The sorted array is ");
        System.out.println(Arrays.toString(nums));
    }
}

実行結果

The original array contains
[6, 78, 90, -12, -45, 0, -1, 45]
The sorted array is
[-45, -12, -1, 0, 6, 45, 78, 90]

コードの解説

comb_sortメソッドの仕組み

Demoクラス内には「comb_sort」メソッドが定義されています。まず配列の長さを初期ギャップとして取得し、その値が1より大きい間は、長さを縮小係数「1.3f」で割った値を新しいギャップ「len_gap」として設定します。

次に配列を先頭から走査し、「i番目の要素」と「i + len_gap番目の要素」を比較します。前者が大きければswapメソッドを使って両者を交換し、交換が発生したことを示すフラグを立てます。ギャップが1まで縮小すると、実質的にはバブルソートと同じ動作になり、交換が一切発生しなくなった時点でソート完了となります。

mainメソッドの流れ

mainメソッドでは、負の値を含む整数配列を用意し、Arrays.toString()で元の配列の内容を出力します。その後、Demoクラスのインスタンスを生成してcomb_sortメソッドを呼び出し、ソート後の配列を再び出力しています。実行結果から、昇順に正しく整列されていることが確認できます。

計算量の目安

コムソートの平均計算量は O(n log n) 程度とされ、最悪の場合でも O(n²) よりはるかに良好な性能を発揮します。追加のメモリ領域をほとんど必要としないインプレースなアルゴリズムである点も大きな特徴です。