Studencheskie Programmisty

BogosortをJavaScriptで実装してみた

Jan 31, 2011

暇でWikipedia見てたらボゴソートとかいうのを見つけた。JavaScriptでの実装例があまりないようだったので、どうせだからと実装してみることにした。

ちなみに、ボゴソートとは「要素をシャッフル→ソートされてたら処理終了、されてなければまたシャッフル」を繰り返す、非常に効率の悪いアルゴリズムである。

function isSorted(aArray){
   for(var i=0,l=aArray.length-1;i<l;i++){
      if(! (aArray[i] <= aArray[i+1])) return false;
   }
   return true;
}

function shuffle(aArray){
   return aArray.sort(function(){
      return Math.random()*100 <= 50;
   });
}

function bogoSort(aArray){
   while(!isSorted(aArray)){
      shuffle(aArray);
   }
}

追記。sortでシャッフルすると偏るらしいです。

シマンテックストア

    Writebacks

    スパム対策のため、コメント・トラックバックは閉鎖しました。