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

4.3

 ヒープソート

■

67

void *tmp = ar[i];

ar[i] = ar[maxPos];

ar[maxPos] = tmp;

}

}

}

選択ソートは本章で述べる整列アルゴリズムの中で最も遅い。最良の場合（すな

わち、配列が既に整列されている場合）でも二乗時間かかる。ほとんど同じ作業を

一切学習せずに繰り返す。

A

の最大要素

max

の選択には、

n

−

1

回の比較が要り、

2

番目の最大要素の選択には

n

−

2

回の比較が必要なので、進歩が少ない。この比較

の多くは、無駄になっている。なぜなら、要素が2番目より小さいなら、最大要素

でないのだから、最大要素にはなり得ないし、

max

の計算に関係しない。この性能

が悪いアルゴリズムを詳しく述べるのはやめて、選択ソートの背後にある原則をさ

らに効果的に使えることを示す

ヒープソート

について次に述べよう。

4.3

 ヒープソート

n

要素の非整列配列

A

の最大要素を見つけるには、少なくとも常に

n

−

1

回の比較

が必要だが、直接比較する要素の個数を最小化できないものだろうか。例えば、ス

ポーツのトーナメントでは、

n

個のチームから「ベスト」チームを決めるのに、優勝

者は他の

n

−

1

チームすべてと試合をするわけではない。米国で最も有名なバスケッ

トボールの試合の

1

つに、

NCAA

チャンピオンシップ・トーナメントがあるが、こ

れは、本質的には全米

64

大学のチームが競う

＊

1

。最終的に優勝チームは、決勝戦に

出るまでに

5

つのチームと試合をするので、

6

回勝たないといけない。

6

＝

log (