So-net無料ブログ作成

選択ソートで数字を昇順に並び替えるシミュレーション [メール投稿]

正己さんはTwitterを使っています: "(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16)をランダムに並び替えた後に、二つの数字を入れ替える作業を何度行ったら元の順番に戻るか。並び方で異なるはずだが、それぞれの最小回数の手順を求める方法がありそうだけどなぁ。私の頭では解けそうにない。"
...

 ほぼ一日中考えていたのだが、最小回数の手順は1番から順に元の位置に戻せば良いだけかもしれない。
 ググって調べていたら、その方法は「選択ソート」と呼ぶらしい。
 選択ソートをJavascriptでシミュレーションしてみたくなったので、【【Javascript】配列の順序のランダム入れ替え at softelメモ】の「Fisher-Yatesというアルゴリズムを使った例」を使って数字を並び替えて、【配列内のデータをソートする(選択法)】のスクリプトを少し改造して作ってみた。スクリプトを次の通り。
<script type="text/javascript">
<!--
Array.prototype.shuffle = function(){
  var i = this.length;
  while(i){
   var j = Math.floor(Math.random()*i);
   var t = this[--i];
   this[i] = this[j];
   this[j] = t;
  }
  return this;
}
function sortData(){
  var c=0;
  for (i=0; i<data.length-1; i++){
    for (j=i+1; j<data.length; j++){
//    if (data[j] < data[i]){
      if (data[j] < data[i] && data[j]==Math.min.apply(null, data.slice(i))){
        n = data[j];
        data[j] = data[i];
        data[i] = n;
        c = c+1;
        document.write(c+"回目:"+data[i]+"⇔"+data[j]+":");
        for (k=0; k<data.length; k++) document.write(data[k],", ");
        document.write("</br>");
      }
    }
  }
}
function printArray(){
  for (i=0; i<data.length; i++) document.write(data[i],", ");
  document.write("</br>");
}
data16 = new Array(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16);
data9 = new Array(1,2,3,4,5,6,7,8,9);
data = data9.shuffle();
document.write("ソート前:</br>");
printArray();
document.write("</br>ソート:</br>");
sortData();
document.write("</br>ソート後:(昇順)</br>");
printArray();
// -->
</script>

結果は次の通り。数字を16個も並べると見づらいので、data16ではなく9個の数字を並べたdata9を使ったシミュレーション。

nice!(0)  コメント(0)  トラックバック(0) 
共通テーマ:moblog