アルゴリズムクイックリファレンス 第2版

72

■

4

章 整列アルゴリズム

4.3.1

 文脈

ヒープソート

は、安定ソートではない。

ヒープソート

は、

クイックソート

が（ほと

んど困惑させられるほど）うまくいかない状況の多くを回避できる。それでも、平均

時の

クイックソート

は、

ヒープソート

より性能が良い。

4.3.2

 解

C

による実装例を例4-4に示す。

例

4-4

 

C

によるヒープソート実装

static void heapify (void **ar, int(*cmp)(const void *,const void *), int idx, int max) {

int left = 2*idx + 1;

int right = 2*idx + 2;

int largest;

/* A[idx], A[left], A[right]

の最大要素を見つける

*/

if (left < max && cmp (ar[left], ar[idx]) > 0) {

large

st = left;

} else {

largest = idx;

}

if (right < max && cmp(ar[right], ar[largest]) > 0) {

largest = right;

}

/*

最大要素が親でなかったら入れ替えて、子についてもその操作を続ける。

*/

if (largest != idx) {

void *tmp;

tmp = ar[idx];

ar[idx] = ar[largest];

ar[largest] = tmp; ...