話題のソートアルゴリズム「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分で書けたあたりが、
このアルゴリズムのすごいところかも。