Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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

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

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

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

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

5 レポートおよび課題の提出 ・レポート名はt0629xx.docとし、以下の項目を含むこと。 ・課題1のソースリスト ・課題1の出力
・課題2のソースリスト ・課題2の出力 ・課題2の考察 課題の出力については、出力画面ウィンドウのダンプ、もしくは出力画面からのテキストコピーのどちらでも良い。 上記のファイルをコースナビのデータ構造とアルゴリズム(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 ヒープソートの原理 リストL 2,9,5,6,… 1.ヒープ(半順序木)を作る(優先度つき待ち行列に入れる)
2.以下の処理を繰り返して並べかえる ヒープの先頭の要素と末尾の要素を交換 [先頭]~[末尾-1]の部分の半順序を回復させる 優先度つき 待ち行列 リストL 2,9,5,6,…

8 1.ヒープを作る 部分木の根の要素を適切な位置まで下げる操作を繰り返すことで,半順序木をボトムアップに構築する 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 2.並べかえ 2-1 半順序木の根と右端の葉を交換 10 5 6 8 9 18 3 15 11 12 20 10 5 6 8 9 18 12
2-1 半順序木の根と右端の葉を交換 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、右の子はそのひとつ後ろにある
2.並べかえ(つづき) この部分の 半順序を 回復させる 2-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 プログラムの概要 1.ヒープ(半順序木)を作る 2.以下の処理を繰り返す begin heapsort
ヒープの先頭の要素と末尾の要素を交換 トップダウンに[先頭]~[末尾-1]の部分の半順序を回復させる heapsort heapify downMin deleteMin downMin end


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

Similar presentations


Ads by Google