ヒープソート ( JavaScript )

ええと、ヒープソートです。

実は、一度書いたのですが、ヒープソートのメリットが全然活かせてなかったのでボツにしました。

ちょっと勘違い。

ヒープの構築(2分木の作成)と要素の取り出しを繰り返せばヒープソートだと思ってたのですが、毎回 木全体を作り直してしまうと遅いですよね。

というわけで、やり直しです。

  001: var count = 10;
  002: var nums = new Array(count);
  003: 
  004: // 適当な数値で初期化 ( 重複OK )
  005: if (var c = 0; c < count; c++) {
  006:   nums[c] = Math.floor((Math.random() * 100) % 100);
  007: }
  008: 
  009: // ヒープ構造の初期化
  010: for (var c = Math.floor(count / 2); c >= 0; c--) {
  011:   heap(c, count);
  012: }
  013: 
  014: // 入れ替え＆ソート
  015: for (var c = count - 1; c >= 0; c--) {
  016:   var x = nums[c];
  017:   nums[c] = nums[0];
  018:   nums[0] = x;
  019:   heap(0, c);
  020: }
  021: 
  022: // 特定のノード以下の木構造を再構築
  023: function heap(node, cnt) {
  024:   var p = (node + 1) * 2 - 1;
  025:   if (p > cnt) return;
  026: 
  027:   if((nums[node] < nums[p]) && 
  028:       ((p == (cnt - 1)) || (nums[p] > nums[p + 1]))) {
  029:     // 左側の葉と入れ替え
  030:     var x = nums[p];
  031:     nums[p] = nums[node];
  032:     nums[node] = x;
  033:     heap(p);
  034:   }
  035:   else if (((p + 1) < cnt) && (nums[node] < nums[p + 1])) {
  036:     // 右側の葉と入れ替え
  037:     var x = nums[p + 1];
  038:     nums[p + 1] = nums[node];
  039:     nums[node] = x;
  040:     heap(p + 1);
  041:   }
  042: }

最大値となる根を抜き出した後は、ヒープの末端の葉を正しい位置に入れてあげればOKってことですね。ヒープを全て作り直すのとは、速度は大きく違いますね。

0

1

2

3

4

5

0

1

2

3

4

5

ソートを試してみる