目次へ

9.ソーティング(ヒープソート)

9.1.ヒープソート

選択ソートとバブルソートは計算量がO(n2) (計算量がデータ数の2乗に比例する)で実行時間が非常にかかるので、実際にはほとんど使用されません。ここでは計算量がO(nlogn) ですむ「ヒープソート」を解説します。

「ヒープ」とは2分木(1つの節から伸びる枝の本数が2本以下である木)で、自分の値が子の値よりも必ず大きい(小さい)ものを言います。下図は自分の値が子の値よりも必ず小さいヒープです。

ヒープの図

上図のように節および根に番号をふったヒープを 配列で表現すると、a[n]の子はa[2n+1]とa[2n+2]、a[n]の親はa[(n-1)/2]となります。

9.2.ヒープの作成

自分の値が子の値よりも必ず小さいヒープの作成方法について説明します。ここで下図のようなAを根とする部分木を考えます。BおよびCを根とする部分木は既にヒープになっているとします。この状態でAにあるデータαに対して以下の操作を繰り返すと、Aを根とする部分木全体もヒープになります。

  1. 子であるBとCのデータのうち、小さいほうのデータをβとします。二つを比較しα>βなら入れ替えます。そうでないなら処理を終了します。
  2. 入れ替えた後、再びαと、その子2つの内小さいほうのデータγとを比較します。もしα>γなら入れ替え、そうでないならば処理を終了します。
  3. 比較する子供がいなくなるか、処理が終了するまで2を繰り返します。

つまり「αが2つの子のデータと比較して、一番小さくないならば入れ替え」という処理を、子供がいなくなるか終了するまで繰り返します。

Aを根とする部分木の図

最初はどの部分木もヒープではありませんが、一番末端の右端にある部分木(9.1の図の場合は「4」を根とする部分木)から順に上記の処理を実行していけば、木全体がヒープになります。

9.3.ソーティングの実行

ヒープができても、ソーティングはまだ完成していません。「9.1」の図はヒープですが、配列内のデータは順番に並んでいません。ヒープからデータを順番に並べるためには次のようにします。

ヒープでは根にあるデータが最も小さいので、このデータを取り除きます。そして空いた根の部分に、最も末端の右端にあるデータを移してきます。「9.1」図の場合は、9のデータ「88」を0に移すので、以下のようになります。

ヒープソートの図

この状態は「9.2」図と同じ状態で、1および2を根とする部分木はヒープになっていますが、全体はヒープになっていません。これに対して「9.2」と同じ処理を繰り返すと再びヒープになります。

この処理をデータがなくなるまで繰り返していくと、データを小さい順に取り出していくことができます。これがヒープソートのアルゴリズムです。

(実習課題)

以下のプログラムを作成しなさい。

  • 乱数発生プログラムで生成した数字を読み込み、それに対してヒープソートを実行する。
解答例をダウンロード  1 2

↑このページの先頭へ

こちらもチェック!

PR
  • XMLDB.jp