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

話題のソートアルゴリズム「sleep sort」をJavascriptで実装したよ

「sleep sort」については以下のリンクを見てもらうとして
4chan BBS - Genius sorting algorithm: Sleep sort常識を覆すソートアルゴリズム!その名も"sleep sort"! - Islands in the byte streamはてなブログBig Sky :: Sleep sort in Go


まず本題のコード

function sleepSort(array, callback, f){
    var l = array.length, result = [];
    var i = l;
    
    if(f == null)
        f = Number;
    
    while(i--) (function(value){
        setTimeout(function(){
            result.push(value);
                if(--l === 0)
                    callback(result);
        }, f(value));
    })(array[i]);
}


arrayにソートしたい配列、
callbackにコールバック関数、
fに配列の値を数値に変換する関数(省略可)
をそれぞれ指定するとcallbackにソートされた結果が渡されます。


値が負だったり実数だったりすると、
ちょっと工夫しないと使えません。


勢いで書いたコードなので、
whileの中で匿名関数使っているなどの問題もあります。
そもそも、このアルゴリズムに使いどころがあるのか疑問ですが。


最後にサンプル

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <script>
        function sleepSort(array, callback, f){
            var l = array.length, result = [];
            var i = l;
            
            if(f == null)
                f = Number;
            
            while(i--) (function(value){
                setTimeout(function(){
                    result.push(value);
                    if(--l === 0)
                        callback(result);
                }, f(value));
            })(array[i]);
        }
        
        window.onload = function(){
            function randint(){ // ランダムな256未満の整数
                return Math.random() * 256 | 0;
            }
            
            var array = [], i = 100; // ランダムな整数100個の配列を作る
            
            while(i--)
                array.push(randint());
            
            // もとの配列を表示 (before : 〜)
            document.getElementById('array').textContent =
                JSON.stringify(array, null, 4);
            
            // ソート
            sleepSort(array, function(result){
                // 結果を表示 (after : 〜)
                document.getElementById('result').textContent =
                    JSON.stringify(result, null, 4);
            });
        };
    </script>
    <style>
        div { margin: 1em 0 }
        #array::before { content: 'before :' }
        #result::before { content: 'after :' }
    </style>
</head>
<body>
    <div id="array"></div>
    <div id="result"></div>
</body>
</html>


ここまで30分で書けたあたりが、
このアルゴリズムのすごいところかも。