【Unity/C#】コムソートとは(コード付き)

コムソートとは

コムソートはバブルソートの改良版です。
安定ソートではないため場合によっては処理が多くなってしまいますが基本的には早いです。

アルゴリズム

1. 総数 n を 1.3 で割り、小数点以下を切り捨てた数を間隔 h とする。 i=0 とする。
2. i 番目と i+h 番目を比べ、i+h 番目が小さい場合入れ替える。
3. i=i+1 とし、i+h>n となるまで3を繰り返す。
4. hがすでに1になっている場合は入れ替えが発生しなくなるまで上の操作を繰り返す。
5. h を 1.3 で割り、小数点以下を切り捨てた数を新たに間隔 h とし、操作を繰り返す。

実行結果

サンプルコード

    int[] ComdSort(int[] _array)
    {

        // 交換したかのチェックフラグ
        bool isChanged = false;

        // 櫛の間隔を定義します。
        int h = _array.Length;


        // コムソートで配列の中身を昇順で並べ替えます。
        while (isChanged || h > 1)
        {

            // 櫛の間隔を計算します。
            if (h > 1)
            {
                h = Mathf.FloorToInt(h / 1.3f);
            }

            isChanged = false;
            for (int i = 0; i < _array.Length - h; i++)
            {
                // 指定した間隔の要素と比較し、順序が逆であれば入れ替えます。
                if (_array[i] > _array[i + h])
                {
                    // 配列の要素の交換を行います。
                    int temp = _array[i];
                    _array[i] = _array[i + h];
                    _array[i + h] = temp;

                    // 交換フラグをtrueにします。
                    isChanged = true;
                }
            }
        }
        return _array;
    }

まとめ

交換ソートの中では比較的に早いですが安定はしていませんのでたまにソートが遅くなります。
交換ソートの中では比較的に早いです。