ヒープソート(Heap Sort)アルゴリズム実装C言語版

2008年10月18日13:52
Slyar
コメント
コメントを読む
作者:Slyar文章来源:Slyar Home(www.slyar.com)転載ご明記ください.ご協力ありがとうございます.
n個のキーワードシーケンスKl,K 2,...,Knをヒープ(Heap)と呼び、このシーケンスが以下の特性(略称ヒープ特性)を満たす場合にのみ、
ki≦K 2 i、ki≦K 2 i+1またはKi≧K 2 i、ki≧K 2 i+1(1≦i≦n)
このシーケンスに格納されたベクトルR[1.n]を完全二叉木の格納構造と見なすと、スタックは実質的に以下の性質を満たす完全二叉木である:ツリー内のいずれの非葉接点のキーワードもその左右の子供(存在する場合)接点の関鍵字より大きくない(または小さくない).(すなわち、ツリーを線形に格納すると、下降しないシーケンスまたは上昇しないシーケンスが得られる)
SLYARはアルゴリズムを整理し、C言語で実現し、コメント付きです.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

void sift(int a[],int i,int n) /* i    ,n      */
{
    int child,tmp;
    for (tmp=a[i];n>2*i;i=child)
    {
        child=2*i; /* i     2*i,    2*i+1 */
        if (child!=n-1&&a[child+1]>a[child]) /*  child           */
        {
            child++;
        }
        if (tmp<a[child]) /*         */
        {
            a[i]=a[child]; /*            */
        }
        else break;
    }
    a[i]=tmp; /*          */
}

void heapsort(int a[],int n) /*  a[1...n]     */
{
    int i,tmp;
    for (i=n/2;i>=0;i--) /*       */
    {
        sift(a,i,n);
    }
    for (i=n-1;i>0;i--) /*   n-1    */
    {
        tmp=a[0]; /*               */
        a[0]=a[i];
        a[i]=tmp;
        sift(a,0,i); /*  a[1..n-1]     */
    }
}