忍者ブログ
2ヶ月弱で情報処理試験・ソフトウェア開発技術者に合格します。
★RSS 1.0  ★RSS 2.0
Posted at 2018.07.22,Sun
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

Posted at 2007.10.09,Tue
ええと、ヒープソートです。

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

ちょっと勘違い。

ヒープの構築(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


ソートを試してみる
PR
Comments
Post a Comment
Name :
Title :
E-mail :
URL :
Comments :
Pass :   Vodafone絵文字 i-mode絵文字 Ezweb絵文字
TrackBack URL
TrackBacks
Welcome ...

 
Ad.
Profile
名前:たびと。
職業:元腐れプログラマ

Template by mavericyard*
忍者ブログ [PR]