配列内のデータをソートする(ヒープソート)

説明

ソート方法の1つにヒープソートがあります。ヒープ(二分木)を作成し再構成していくことでソートを行います。

サンプルプログラム

var data = new Array(30,10,5,99,44,65,13,31,1,57,88,78);
function sortData(data) {
var j;
data[data.length] = data[0];
var N = data.length-1;
for (var k=N; k>0; k--) {
var i = k;
var n = data[i];
while ((j = i*2) <= N) {
if ((j<N) && (data[j] < data[j+1])) j++;
if ( n >= data[j]) break;
data[i] = data[j];
i = j;
}
data[i] = n;
}
while (N > 1) {
n = data[N];
data[N] = data[1];
N--;
i = 1;
while ((j = i*2) <= N) {
if ((j < N) && (data[j] < data[j+1])) j++;
if (n >= data[j]) break;
data[i] = data[j];
i = j;
}
data[i] = n;
}
for (i=0; i<data.length-1; i++) data[i] = data[i+1];
data.length--;
}
document.write("ソート前:"+data.toString()+"<br>");
sortData(data);
document.write("ソート後:"+data.toString()+"<br>");
サンプルを実行
[戻る]