ヒープソートの演習 第13回
課題１ ヒープソートのサンプルプログラム（heapsort.pdf参照）は、ヒープソートを用いてデータを降順にソートする．これを実行すると以下のような結果が出力される このサンプルプログラムおよび教科書図4.7(p.95)を参考に、次ページの要求を満たすヒープソートのプログラムを作成しなさい
課題１の続き ・15個の整数 {29, 5, 4, 23, 6, 63, 12, 2, 53, 12, 33, 34, 14, 23, 37} を昇順にソートする。 ・ソート前のデータ列と、ソート後のデータ列を出力する。 ・ソート後のデータ列を表示後、プログラム実行時にデータの交換 swap()と最大要素の出力と除去 deletemax()が何回呼び出されたか 出力する。 ・ソースファイル名は、t0629xx_hs.c とする。 （t0629xxは自分の学籍番号）
課題２ ・課題１のプログラムを修正して，乱数生成関数rand()を用いて発生 させた最大64000個の整数データをソートし，ソートにかかる時間 を測定できるようにせよ． （演習I 課題３で学んだclock関数を使用するとよい．) ・データ列は表示しないでよい． ・ソースファイル名は，t0629xx_hs2.cとする． ・データ数nをいろいろ変えて実行し，各々のnにおいて、ソートにかか る時間が、O(n2)，O(nlogn)，O(n)のどれに近いかを考察せよ。
レポートおよび課題の提出 ・レポート名はt0629xx.docとし、以下の項目を含むこと。 ・課題１のソースリスト ・課題１の出力 ・課題２のソースリスト ・課題２の出力 ・課題２の考察 課題の出力については、出力画面ウィンドウのダンプ、もしくは出力画面からのテキストコピーのどちらでも良い。 上記のファイルをコースナビのデータ構造とアルゴリズム（7/23）の レポートとして提出（アップロード）する。 〆切： 2008/8/6(水) 18時
ヒープソート(heap sort)(p.94) ヒープを用いてデータの整列を行うアルゴリズム 計算量 O (n log n) ヒープ : 配列により半順序木を実現したもの 常に子が親より 大きい木の例 常に子が親より 小さい木の例 3 10 5 9 8 9 6 8 9 10 6 3 7 6 10 18 9 4 1 2
ヒープソートの原理 リストＬ ２，９，５，６，… １．ヒープ（半順序木）を作る（優先度つき待ち行列に入れる） ２．以下の処理を繰り返して並べかえる ヒープの先頭の要素と末尾の要素を交換 [先頭]～[末尾-１]の部分の半順序を回復させる 優先度つき 待ち行列 リストＬ ２，９，５，６，… ９ ６ ５ ２
１．ヒープを作る 部分木の根の要素を適切な位置まで下げる操作を繰り返すことで，半順序木をボトムアップに構築する 10 6 9 5 15 15 ← a[0] 要素数 n = 15 6 9 5 15 15 12 ← a[n/2-1] (=a[6]) 3 18 9 8 11 9 20 10 ← a[n-1] (=a[14])
２．並べかえ ２－１ 半順序木の根と右端の葉を交換 10 5 6 8 9 18 3 15 11 12 20 10 5 6 8 9 18 12 ２－１ 半順序木の根と右端の葉を交換 10 5 6 8 9 18 3 15 11 12 20 10 5 6 8 9 18 12 15 11 3 20 [0] [n-1] a 12 5 9 6 8 9 10 10 18 9 15 11 15 20 3
着目する節点の左の子は2*i+1、右の子はそのひとつ後ろにある ２．並べかえ（つづき） この部分の 半順序を 回復させる ２－１ 残りの部分の半順序の回復 10 5 6 8 9 18 12 15 11 3 20 子が親より小さい間， 2つの子のうち 小さい方の子 と親を交換していく この部分のヒープを再構成 [0] [1] [2] [3] [4] [7] [8] [n-2] [n-1] a 12 5 9 6 8 9 10 10 18 9 15 11 15 20 5 12 6 10 3 着目する節点の左の子は2*i+1、右の子はそのひとつ後ろにある
プログラムの概要 １．ヒープ（半順序木）を作る ２．以下の処理を繰り返す begin heapsort ヒープの先頭の要素と末尾の要素を交換 トップダウンに[先頭]～[末尾-１]の部分の半順序を回復させる heapsort heapify downMin deleteMin downMin end