サイトマップ / Ｃ言語講座＞出入り口＞総目次＞目次：ソート＞ヒープソート
/* 今日は２分木 ( ヒープ ) というデータ構造のうち、半順序木を使って行う、高速なソートのアルゴリズムであるヒープソートについて学びます。
２分木というデータ構造については、既に、学んでいますが、復習します。下記の node[ ] という配列の添字 ０ は使いませんので、それは無視して下さい。数字を斜めの線で結んでいませんが、１と ２、１ と ３、２ と ４、２ と ５、３ と ６、３ と ７ が、線で結ばれているものとします。
int node[ ] = {0,
1,
2, 3,
4, 5, 6, 7,
};
このようなデータ構造を、枝が一度に二つに分かれる木に見立てて、２分木といいます。一つ下の二つの要素を子、一つ上の要素を親といいます。一番上の要素を根といいます。つまり、２分木は逆さに生えている木です。
２分木では、親の値は子の値より小さく、左の子の値は右の子の値より小さいという規則があります。
数字の並び方を良く見て下さい。この配列は配列の値と添字の値が一致しています。親の値を ２ 倍すると、左下の子になります。親の値の ２ 倍に１ を足すと右下の子になります。従って、node[n] の左下の子は node[2n] となり、右下の子は node[2n + 1] になります。半順序木では、単に、親の値は子の値より小さいというだけで、子同志の値の大きさは問題にしません。
今回は、後に、ヒープソートを行う都合上、降順の半順序木を作ります。下記に例を示します。
int a[ ] = {0,
86
58 19
51 49 10 15
};
ソースプログラムでは、0 から 99 までの整数の乱数を発生させ、それを int 型の配列 a[ ] にしまいます。次いで、半順序木の構造にします。半順序木の根はその配列の最大値なので取り出します。その位置に、配列の末尾の要素を置きます。半順序木の構造が壊れたので、再び半順序木を構成します。
上記の処理を要素がなくなるまで続ければ、ソートが完了します。具体例を下記に示します。
初期状態
58
15 51
10 19 86 49
最下段の 10 19 86 49 は子がないので、半順序木になっています。そこで、51 を半順序木の根とみなして、子と比較します。比較対象は子の大きい方です。51 と 86 を比較すると、86 の方が大きいので入れ替えます。
58 15 86 10 19 51 49
次いで、86 と 15 の大きい方と、その親と比較します。86 の方が大きいので入れ替えます。
86 15 58 10 19 51 49
次に、15 を根とみなして、子の大きい方の要素と比較します。19 の方が大きいので、入れ替えます。
86 19 58 10 15 51 49
次に親と比較します。親の方が大きいので、入れ替えはしません。これで、半順序木になりました。ここまでが、ソートの準備です。
半順序木の根はそれを構成する要素の最大値です。根の 86 を取り出します。86 のあった位置に、配列の添字の一番大きい要素である 49 を置きます。取り出した 86 は 49 のあった位置におきます。
49 86 19 58 10 15 51
半順序木の構造が壊れたので、半順序木に再構成します。49 の子の大きい方と比較すると、58 の方が大きいので交換します。
58 86 19 49 10 15 51
49 には子が一つしかありません。49 と 51 を比較すると、51 の方が大きいので交換します。
58 86 19 51 10 15 49
これで半順序木になりました。半順序木の根は最大値なので取り出して、その位置に配列の添字の一番大きい要素である 49 を置きます。取り出した 58 は 49 のあった位置に置きます。
49 58 86 19 51 10 15
同様な操作を繰り返すと、順次最大値から取り出して半順序木の末尾に置くので、配列を前から見ると、昇順にソートしたことになります。 */
#include <stdio.h>
#include <stdlib.h> /* rand( ) で必要 */
#define NUM_DATA 20
int a[NUM_DATA + 1];
void SetData(void);
void Hpsort(int a[ ], int n);
void DownHeap(int a[ ], int top, int bottom);
void Swap(int a[ ], int i, int j);
void ShowData(int a[ ], int n);
void main(void);
/* 0 から99 の範囲の整数の乱数をNUM_DATA個作って a[ ] にしまう */
void SetData(void)
{
int i;
for (i = 0; i <= NUM_DATA; i++)
a[i] = rand( ) % 100;
}
/* ヒープソートを行う */
void Hpsort(int a[ ], int n)
{
int leaf, root;
leaf = n; /* 初期値は末尾の要素 */
root = n/2; /* 初期値はその親 */
while (root > 0 ) { /* 半順序木を構成 */
DownHeap(a, leaf, root);
root--;
}
printf("半順序木を構成:\n");
ShowData(a, NUM_DATA); /* できあがった半順序木を表示 */
while(leaf > 0) {
Swap(a, 1, leaf); /* 半順序木の根と末尾の要素を交換 */
leaf--; /* 末尾の要素を半順序木から外す */
DownHeap(a, leaf, 1); /* 半順序木を再構成する */
}
}
/* 半順序木 ( ヒープ ) を構成する */
void DownHeap(int a[ ], int leaf, int root)
{
int i;
i = root * 2;
while (i <= leaf) {
if (i < leaf && a[i + 1] > a[i]) /* a[i] と a[i + 1] の大きい方と */
i++;
if (a[root] >= a[i]) /* a[root] と比較 */
break; /* 子の方が大きければ */
Swap(a, root, i); /* 交換 */
root = i; /* 更にその子についても調べる */
i = root * 2;
}
}
/* 配列の要素を交換する */
void Swap(int a[ ], int i, int j)
{
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/* 配列の要素を表示する */
void ShowData(int a[ ], int n)
{
int i;
for (i = 1; i <= n; i++) {
printf("a[%2d] = %2d ", i, a[i]);
if(!(i % 5)) /* 要素を５つ表示したら改行 */
printf("\n");
}
printf("\n");
}
void main(void)
{
SetData( );
printf("ソート前:\n");
ShowData(a, NUM_DATA);
Hpsort(a, NUM_DATA);
printf("ソート後:\n");
ShowData(a, NUM_DATA);
}
|
/* プログラムを実行すると、乱数の配列と、構成された半順序木の配列と、ソート後の配列が表示されます。配列の添字から親子関係を確認し、半順序木になっていることを確認して下さい。 */
/* (C) 2000- ＹＦプロ. All Rights Reserved. */ 提供：Ｃ言語講座−それ自体コンパイルできる教材を使った講座です−