Presentation is loading. Please wait.

Presentation is loading. Please wait.

4.3 マージソート.

Similar presentations


Presentation on theme: "4.3 マージソート."— Presentation transcript:

1 4.3 マージソート

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 - 1

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

7 ヒープとは この部分木で一番 大きい値は根の14 この部分木で一番 大きい値は根の10 16 14 10 11 9 3 8 6 4 2
どの部分木でもその中で 一番大きい値は根にある

8 ヒープとは 10 2 4 8 9 5 6 7 3 1 h[i]⇔v 6 14 11 4 2 9 3 8 10 16 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)


Download ppt "4.3 マージソート."

Similar presentations


Ads by Google