comb sort(コムソート)

何を探してたかは忘れたけどGoogleで適当に検索してたらcomb sort(コムソート)というものを発見。そしてcomb sortで検索したらいろんな人がこのソートの説明をしていてソースもいろいろあった。

とりあえず、これはバブルソートを改良したものらしい。とても遅いバブルソートを改良したものが、クイックソート並の速さを持ってしまったらしい。とりあえず↓のページのCで書かれたソースをJavaに変換してみた。
http://motoyuki.bsdclub.org/d/d200005c.html#26

それでランダムな１０万個の整数を保存したファイルを読み込みint型の配列にして、javaのライブラリにあるクイックソートを（java.util.Arraysのsort）と速度の比較をしてみた。ここでの時間は単位は秒でそれぞれ10回ずつ計ってその平均時間です。

java.util.Array#sort	0.039秒
combsort	0.051秒

うーん、もっと大きい配列で実行すれば良かったと思ったけど、コムソートの方が遅い、違うデータでやればどうなるかわからないけど。ただ、コムソートは高速化ができて高速化を行うことでクイックソートよりも速くソートができるらしい。(ヒープソート並の速度らしいです)

//以下ソース

public class CombSort{

    public static void combsort (int data[])

    {

        int size = data.length;

        int hold;

        int gap  = size;

        boolean done = false;
        while ((gap > 1) || !done) {

            gap = (gap * 10) / 13;

            if (gap == 0)

                gap = 1;
            done = true;

            for (int i = 0; i < size - gap; ++i) {

                if (data[i] > data[i + gap]) {

                    hold = data[i];

                    data[i] = data[i + gap];

                    data[i + gap] = hold;

                    done = false;

                }

            }

        }

    }

}