４．３　マージソート

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

マージソート ソートしたいデータを前半、後半に分割 前後半をマージソートでソート 前半と後半をマージ （合併） 前半と後半をマージ　（合併） 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

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

再帰方程式の計算 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

４．４　ヒープソート

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

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

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

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

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

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

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

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

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

ヒープソート 最悪時間計算量 ⇒ 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)

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

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

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

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

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

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

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

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

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

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

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

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

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