読者です 読者をやめる 読者になる 読者になる

くろねこ日記

ソフトウェアに関する技術メモが多いです.

ソートは寝て待つスリープソート

久々

前回の日記更新から1年以上も経ちました。
twitterのソフトはとりあえず完成しました(もちろんAuth認証で)。その辺の話はまた今度します。

今回はスリープソートという面白いアルゴリズムが4chから誕生したようなので、Javaのスレッド処理の勉強も兼ねて書いてみました。
元ネタ:http://dis.4chan.org/read/prog/1295544154

スリープソートとは

一言で言えばスリープさせる時間を利用して昇順にソートを行うアルゴリズムです。
スリープソートの流れ図を示しました。
f:id:kuroneko0208:20110522204158p:image
着目すべきはソートされる値によってスリープから起床までの時間が異なることです。
このアルゴリズムの特徴はソート対象の値が小さいと起床が速いため大きい値よりも先に出力されるということです。
つまりソート対象の値に大きな数字であればあるほどソートに時間が掛かるわけで、さらにスレッドもソートされる数だけ生成するのでメモリも多く使いそうです。
でもCPUに負担をかけないという意味ではとてもPCにもクリーンかもしれません。それに時間スケールを利用してソートするアルゴリズムはとても面白いです。

プログラム

作成したプログラムを貼付けます。

/**************
*クラス変数   *
***************/
class Globalvar {

    public static int[] iarray = {1, 4, 6, 2, 3};
    public static int index = 0;
}
/***************************************************************************************
*スレッド処理の内容                                                                    *
*(Javaではスレッドを扱う時にはスレッドクラスを継承してrunメソッドをオーバーライドする) *
****************************************************************************************/
class Thread1 extends Thread {

    final int findex = Globalvar.index;

    public void run() {

        try {
            sleep(Globalvar.iarray[findex] * 3);//3掛けないとこのPCだとソートされなかった
            System.out.println(Globalvar.iarray[findex] + ",");
        } catch (InterruptedException e) {
        }
    }
}

public class Sleepsort {

    public static void main(String[] args) {

        /******************
         * スレッド生成・実行*
         ******************/
        for (int i = 0; i < Globalvar.iarray.length; i++) {
            Globalvar.index = i;
            new Thread1().start();
        }

    }
}

ひとこと

このアルゴリズムはJavaの練習にはちょうど良かったです。

それではまた