４．３　マージソート.

Presentation on theme: "４．３　マージソート."— Presentation transcript:

1 ４．３　マージソート

2 マージソート ソートしたいデータを前半、後半に分割 前後半をマージソートでソート 前半と後半をマージ （合併） 6 2 5 3 4 7 1
前半と後半をマージ　（合併） 6 2 5 3 4 7 1 8 2 3 5 6 1 4 7 8

3 マージソート ソートしたいデータを前半、後半に分割 前後半をマージソートでソート 前半と後半をマージ （合併）
前半と後半をマージ　（合併） nデータのマージソートで必要な比較回数をT(n)で表す ⇒　n ⇒　T(n/2)×2 6 2 5 3 4 7 1 8 T(n/2) T(n/2) 6 2 5 3 2 3 5 6 1 4 7 8 4 7 1 8

4 T(n) = 2T(n/2) + n - 1 ⇒ O(n log n)
マージソート ソートしたいデータを前半、後半に分割 前後半をマージソートでソート 前半と後半をマージ　（合併） nデータのマージソートで必要な比較回数をT(n)で表す ⇒　n ⇒　T(n/2)×2 ⇒　n T(n) = 2T(n/2) + n - 1 ⇒ O(n log n) 6 2 5 3 4 7 1 8 T(n/2) T(n/2) 2 2 3 5 6 3 5 6 1 1 4 7 8 4 7 8 n - １

5 再帰方程式の計算 T(n) = 2T(n/2) + n = 2(2T(n/4) + n/2) + n
= 2(2(2T(n/8) + n/4) + n/2) + n … = 2log n + （n + ・・・+ n） = n + （n + ・・・+ n） = c・n log n

6 ４．４　ヒープソート

7 ヒープとは この部分木で一番 大きい値は根の14 この部分木で一番 大きい値は根の10 １６ １４ １０ １１ ９ ３ ８ ６ ４ ２
どの部分木でもその中で 一番大きい値は根にある

8 ヒープとは １０ ２ ４ ８ ９ ５ ６ ７ ３ １ h[i]⇔v ６ １４ １１ ４ ２ ９ ３ ８ １０ １６ h[2i]⇔vの左の子

9 ヒープソート 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する 16
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する 16 14 10 11 9 3 8 4 2 6

10 ヒープソート 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する 14
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する 14 11 10 16 6 9 3 8 4 2

11 ヒープソート 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する 11
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する 11 9 10 16 14 6 2 3 8 4

12 ヒープソート 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する 10
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する 10 9 8 16 14 11 6 2 3 4

13 ヒープソート 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する 9
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する 9 6 8 16 14 11 10 4 2 3

14 ヒープソート 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する 8
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する 8 6 3 16 14 11 10 9 4 2

15 ヒープソート 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する 16
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する 16 14 11 10 9 8 6 4 3 2

16 ヒープソート 最悪時間計算量 ⇒ O(n log n) ⇒ O(n) 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す O(n)
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する O(n) ⇒　O(log n) 最悪時間計算量　 ⇒　O(n log n) 6 14 11 4 2 9 3 8 10 16 O(log n)

17 ヒープの構築 ⇒ O(n) 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す O(n) ⇒ O(log n)
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する O(n) ⇒　O(log n) 2 8 10 11 4 16 9 6 3 14

18 ヒープの構築 ⇒ O(n) 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す O(n) ⇒ O(log n)
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する O(n) ⇒　O(log n) 2 8 10 11 4 16 9 6 3 14

19 ヒープの構築 ⇒ O(n) 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す O(n) ⇒ O(log n)
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する O(n) ⇒　O(log n) 2 8 10 11 14 16 9 6 3 4

20 ヒープの構築 ⇒ O(n) 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す O(n) ⇒ O(log n)
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する O(n) ⇒　O(log n) 2 8 10 11 14 16 9 6 3 4

21 ヒープの構築 ⇒ O(n) 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す O(n) ⇒ O(log n)
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する O(n) ⇒　O(log n) 2 8 16 11 14 10 9 6 3 4

22 ヒープの構築 ⇒ O(n) 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す O(n) ⇒ O(log n)
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する O(n) ⇒　O(log n) 2 14 16 11 8 10 9 6 3 4

23 ヒープの構築 ⇒ O(n) 先ずヒープを作る 以下の操作をデータが無くなるまで繰り返す O(n) ⇒ O(log n)
先ずヒープを作る　　 以下の操作をデータが無くなるまで繰り返す ヒープの根のデータを取り出し、並べる 壊れたヒープを修復する O(n) ⇒　O(log n) 16 14 10 11 8 2 9 6 3 4

24 ヒープ構築がO(n)である証明 高さrの位置にある頂点の数は高々　　　　個

25 ヒープ構築がO(n)である証明 高さrの位置にある頂点の数は高々　　　　個

26 ヒープ構築がO(n)である証明 高さrの位置にある頂点の数は高々　　　　個

27 ヒープ構築がO(n)である証明 高さrの位置にある頂点の数は高々　　　　個

28 ヒープ構築がO(n)である証明 高さrの位置にある頂点の数は高々　　　　個 高さrの位置でかかるコスト

29 ヒープ構築がO(n)である証明 高さrの位置にある頂点の数は高々　　　　個 高さrの位置でかかるコスト 全体のコスト = = O(n)