(構造関連)整列アルゴリズム2

今回は前回に引き続き整列アルゴリズムの効率的手法である、クイックソートとヒープソートを述べる。
まずは、クイックソートから述べる。
クイックソートは前回の単純整列法を改良したものである。配列のindexの中間値にあるデータを基準値とし大小に別けてゆくそしてindexの中間値を更新しながら進めてゆく方式である

#include
void swap(int *,int *);
void quicksort(int,int);

int a[]={3,0,4,2,5,7,6,9,1,8};//並べたい配列

int main(void)
{
int i;
quicksort(0,9);//ソート関数
for(i=0;i<=9;i++)
printf("%d",a[i]);
printf("\n");
}

void swap(int *p,int *q)
{
int tmp;
tmp=*p;
*p=*q;
*q=tmp;
}

void quicksort(int lo,int hi)
{
int i,j,mid,pivot;
if(lopivot)//小さいものを左に
j--;
if(i<=j)//iがjを越えなかったら
{
swap(&a[i],&a[j]);
i++;
j--;
}
}while(i<=j);
//再帰処理で範囲を縮める
quicksort(lo,j);
quicksort(i,hi);
}
}

続いてヒープソートである。
ヒープソートは部分順序付き木(partially ordered tree)
を配列を用いて実現する。配列のindexを算術的に参照可能にすることにより実現可能である。C言語で気をつけるべきところはindexの始点が1ではなく0であるので、木のrootはindex 0で偶数のindexが右側、奇数のindexが左側に来るように表現される。
アルゴリズムは選択法の応用で前回の選択法のforループを配列の後ろからバックしながら行っている。そして木の親子の大小関係を比べて親より子が大きい場合入れ換えを行う。そしてこれを順次行って必ず親より子のほうが小さい「縦の関係」を作る。「縦の関係」とは木の左右の大小関係は無視し、あくまで親子の間だけ大小関係を構成する。
例えば家系図に見立てると自分の叔父叔母が自分より年下でもこの際構わないということである。

#include
void swap(int *,int *);
void downheap(int ,int);
int a[]={3,0,4,2,5,7,6,9,1,8};
int main(void)
{
int i;
for(i=9;i>=0;i--)
downheap(i,9);
for(i=9;i>=0;i--)
{
swap(&a[0],&a[i]);
downheap(0,i-1);
}
for(i=0;i<=9;i++)//recycle "i" and show array data
printf("%d",a[i]);
printf("\n");
return 0;
}

//swapfunction
void swap(int *p,int *q)
{
int tmp;
tmp=*p;
*p=*q;
*q=tmp;
}

void downheap(int k,int r)
{
int j;
for(;;)
{
j=2*k+1;
if(j>r)break;
if(j!=r&&a[j+1]>a[j])j++;
if(a[k]>=a[j])break;
swap(&a[k],&a[j]);
k=j;
}
}