選択ソートで数字を昇順に並び替えるシミュレーション [メール投稿]
正己さんは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>
<!--
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を使ったシミュレーション。