Hatena::Groupjavascript

JavaScriptで遊ぶよ

 | 

2009-03-28

比較関数が正負ランダムを返すソートをしてみる

16:32

我ながらものすごい時間の無駄だった。

半永久的に比較し続けるんじゃないかなーと思ったのだけど。

<html>  
  <head>
    <title>
      Sort with random key
    </title>
  </head>  
  <body>
    <pre>
<script>
  var print = function(text) {
    document.write(text + '\n\n')
  };

  var array = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
  var dup = array.slice();

  print(dup);

  array = array.sort(function(x, y) {

    var rand = ~~ (Math.random() * 10) - 5;

    if (rand < 0) {
      dup[dup.indexOf(x)] = y;
      dup[dup.indexOf(y)] = x;
    }

    print(x + ' <=> ' + y + ' ; key ' + rand);
    print(dup);

    return rand;

  });
</script>
    </pre>
  </body>
</html>

Opera での結果。(もちろん実行するたびに変わる)

a,b,c,d,e,f,g

b <=> a ; random -2

b,a,c,d,e,f,g

c <=> a ; random 0

b,a,c,d,e,f,g

d <=> c ; random -3

b,a,d,c,e,f,g

d <=> a ; random -3

b,d,a,c,e,f,g

d <=> b ; random 4

b,d,a,c,e,f,g

e <=> c ; random -3

b,d,a,e,c,f,g

e <=> a ; random 4

b,d,a,e,c,f,g

f <=> c ; random 3

b,d,a,e,c,f,g

g <=> f ; random 0

b,d,a,e,c,f,g

終了。

左から順に隣りどうしを比べ、交換が起こった場合だけ、そこから左へ順に隣りどうしを比べていく。挿入ソート (あってる?)。

トラックバック - http://javascript.g.hatena.ne.jp/edvakf/20090328
 |