ヒープソートの演習 第13回.

Presentation on theme: "ヒープソートの演習 第13回."— Presentation transcript:

1 ヒープソートの演習 第13回

2 課題１ ヒープソートのサンプルプログラム（heapsort.pdf参照）は、ヒープソートを用いてデータを降順にソートする．これを実行すると以下のような結果が出力される このサンプルプログラムおよび教科書図4.7(p.95)を参考に、次ページの要求を満たすヒープソートのプログラムを作成しなさい

3 課題１の続き ・15個の整数 {29, 5, 4, 23, 6, 63, 12, 2, 53, 12, 33, 34, 14, 23, 37} 　を昇順にソートする。 ・ソート前のデータ列と、ソート後のデータ列を出力する。 ・ソート後のデータ列を表示後、プログラム実行時にデータの交換　 　swap()と最大要素の出力と除去 deletemax()が何回呼び出されたか 　出力する。 ・ソースファイル名は、t0629xx_hs.c とする。 （t0629xxは自分の学籍番号）

4 課題２ ・課題１のプログラムを修正して，乱数生成関数rand()を用いて発生
　させた最大64000個の整数データをソートし，ソートにかかる時間 　を測定できるようにせよ． 　（演習I 課題３で学んだclock関数を使用するとよい．) ・データ列は表示しないでよい． ・ソースファイル名は，t0629xx_hs2.cとする． ・データ数nをいろいろ変えて実行し，各々のnにおいて、ソートにかか 　る時間が、O(n2)，O(nlogn)，O(n)のどれに近いかを考察せよ。

5 レポートおよび課題の提出 ・レポート名はt0629xx.docとし、以下の項目を含むこと。 ・課題１のソースリスト ・課題１の出力
・課題２のソースリスト ・課題２の出力 ・課題２の考察 課題の出力については、出力画面ウィンドウのダンプ、もしくは出力画面からのテキストコピーのどちらでも良い。 上記のファイルをコースナビのデータ構造とアルゴリズム（7/23）の レポートとして提出（アップロード）する。 〆切：　2008/8/6(水)　18時

6 ヒープソート(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

7 ヒープソートの原理 リストＬ ２，９，５，６，… １．ヒープ（半順序木）を作る（優先度つき待ち行列に入れる）
２．以下の処理を繰り返して並べかえる ヒープの先頭の要素と末尾の要素を交換 [先頭]～[末尾-１]の部分の半順序を回復させる 優先度つき 待ち行列 リストＬ ２，９，５，６，… ９ ６ ５ ２

8 １．ヒープを作る 部分木の根の要素を適切な位置まで下げる操作を繰り返すことで，半順序木をボトムアップに構築する 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])

9 ２．並べかえ ２－１ 半順序木の根と右端の葉を交換 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

10 着目する節点の左の子は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 5 12 6 10 3 着目する節点の左の子は2*i+1、右の子はそのひとつ後ろにある

11 プログラムの概要 １．ヒープ（半順序木）を作る ２．以下の処理を繰り返す begin heapsort
ヒープの先頭の要素と末尾の要素を交換 トップダウンに[先頭]～[末尾-１]の部分の半順序を回復させる heapsort heapify downMin deleteMin downMin end