クイックソート.

Presentation on theme: "クイックソート."— Presentation transcript:

1 クイックソート

2 クイックソートの動き ２２ ２７ ７ ２１ ２１ ４７ ６ １０ ３３ ランダムに基準値を選ぶ i と j がすれ違うまで繰り返す
基準値以上の値を検知する 基準値以下の値を検知する i と j がまだすれ違っていなければ A[i]とA[j]を交換する i と j を一歩進める 必要があれば部分問題を解く

3 クイックソートの動き １０ ６ ６ ７ ２１ ４７ ２７ ２２ ３３ ランダムに基準値を選ぶ i と j がすれ違うまで繰り返す
基準値以上の値を検知する 基準値以下の値を検知する i と j がまだすれ違っていなければ A[i]とA[j]を交換する i と j を一歩進める 必要があれば部分問題を解く

4 クイックソートの動き ６ １０ １０ ７ ２１ ４７ ２７ ２２ ３３ ランダムに基準値を選ぶ i と j がすれ違うまで繰り返す
基準値以上の値を検知する 基準値以下の値を検知する i と j がまだすれ違っていなければ A[i]とA[j]を交換する i と j を一歩進める 必要があれば部分問題を解く

5 クイックソートの動き ６ ７ １０ ２１ ４７ ２７ ２７ ２２ ３３ ランダムに基準値を選ぶ i と j がすれ違うまで繰り返す
基準値以上の値を検知する 基準値以下の値を検知する i と j がまだすれ違っていなければ A[i]とA[j]を交換する i と j を一歩進める 必要があれば部分問題を解く

6 クイックソートの動き ６ ７ １０ ２１ ２２ ２７ ４７ ４７ ３３ ランダムに基準値を選ぶ i と j がすれ違うまで繰り返す
基準値以上の値を検知する 基準値以下の値を検知する i と j がまだすれ違っていなければ A[i]とA[j]を交換する i と j を一歩進める 必要があれば部分問題を解く

7 クイックソートの平均時間計算量

8 クイックソートの平均時間計算量

9 クイックソートの平均時間計算量 1/n … 確率 n i ０ n – 1 … 1 n i i - 1 n - i … 1 i n – 1 ０
T（0）時間 T（ｎ－1）時間 … 1 n i i - 1 n - i T（ｉ－1）時間 T（ｎ－ｉ）時間 … 1 i n – 1 ０ T（ｎ－1）時間 T（0）時間

10 クイックソートの平均時間計算量 1 i n – 1 ０ n i - 1 n - i … 1/n 確率 帰納法で証明する T（0）時間

11 バケットソート

12 バケットソート ４ ７ １ ２ ５ ３ バケツ １ ２ ３ ４ ５ ６ ７ ８

13 バケットソート データの個数がnでデータの種類がm 　　　O(n+m)時間

14 辞書式順序 単語a1 a2 …apと単語b1 b2 …bqの間の順序 (a1 a2 …ap)≦(b1 b2 …bq)
　　⇔　1. ∃j　(aj<bj) and (∀i<j ai=bi)　または 2. (p<q) and (∀i≦p ai=bi) 例 　　yamamoto < yamazaki　１のケースでj=5 　　ota < otani　 2のケースでp=3, q=5

15 バケットソートでの辞書式順序 bab bca caa acc +++ 単語キュー 文字キューa 文字キューb 各単語を単語キューに入れる
テンプレートのポインタを右端の文字に合わせる 文字キューc ポインタが文字を指している間は以下を繰り返す 各文字キューを空にする 単語キューが空になるまで以下を繰り返す 単語キューから単語を取出しテンプレートにセットする ポインタが指す文字の文字キューに単語を追加する 文字（アルファベット）順に以下の操作を行う カレントの文字の文字キューの中身を単語キューに追加する テンプレートのポインタを右に一つずらす

16 バケットソートでの辞書式順序 bab bca caa acc +++ 単語キュー 文字キューa 文字キューb 各単語を単語キューに入れる
テンプレートのポインタを右端の文字に合わせる 文字キューc ポインタが文字を指している間は以下を繰り返す 各文字キューを空にする 単語キューが空になるまで以下を繰り返す 単語キューから単語を取出しテンプレートにセットする ポインタが指す文字の文字キューに単語を追加する 文字（アルファベット）順に以下の操作を行う カレントの文字の文字キューの中身を単語キューに追加する テンプレートのポインタを左に一つずらす

17 バケットソートでの辞書式順序 bca caa +++ bab acc 単語キュー 文字キューa 文字キューb 各単語を単語キューに入れる
テンプレートのポインタを右端の文字に合わせる 文字キューc ポインタが文字を指している間は以下を繰り返す 各文字キューを空にする 単語キューが空になるまで以下を繰り返す 単語キューから単語を取出しテンプレートにセットする ポインタが指す文字の文字キューに単語を追加する 文字（アルファベット）順に以下の操作を行う カレントの文字の文字キューの中身を単語キューに追加する テンプレートのポインタを右に一つずらす

18 バケットソートでの辞書式順序 bca caa bab acc +++ 単語キュー 文字キューa 文字キューb 各単語を単語キューに入れる
テンプレートのポインタを右端の文字に合わせる 文字キューc ポインタが文字を指している間は以下を繰り返す 各文字キューを空にする 単語キューが空になるまで以下を繰り返す 単語キューから単語を取出しテンプレートにセットする ポインタが指す文字の文字キューに単語を追加する 文字（アルファベット）順に以下の操作を行う カレントの文字の文字キューの中身を単語キューに追加する テンプレートのポインタを右に一つずらす

19 バケットソートでの辞書式順序 caa bab +++ bca acc 単語キュー 文字キューa 文字キューb 各単語を単語キューに入れる
テンプレートのポインタを右端の文字に合わせる 文字キューc ポインタが文字を指している間は以下を繰り返す 各文字キューを空にする 単語キューが空になるまで以下を繰り返す 単語キューから単語を取出しテンプレートにセットする ポインタが指す文字の文字キューに単語を追加する 文字（アルファベット）順に以下の操作を行う カレントの文字の文字キューの中身を単語キューに追加する テンプレートのポインタを左に一つずらす

20 バケットソートでの辞書式順序 caa bab bca acc +++ 単語キュー 文字キューa 文字キューb 各単語を単語キューに入れる
テンプレートのポインタを右端の文字に合わせる 文字キューc ポインタが文字を指している間は以下を繰り返す 各文字キューを空にする 単語キューが空になるまで以下を繰り返す 単語キューから単語を取出しテンプレートにセットする ポインタが指す文字の文字キューに単語を追加する 文字（アルファベット）順に以下の操作を行う カレントの文字の文字キューの中身を単語キューに追加する テンプレートのポインタを右に一つずらす

21 バケットソートでの辞書式順序 acc +++ bab bca caa 単語キュー 文字キューa 文字キューb 各単語を単語キューに入れる
テンプレートのポインタを右端の文字に合わせる 文字キューc ポインタが文字を指している間は以下を繰り返す 各文字キューを空にする 単語キューが空になるまで以下を繰り返す 単語キューから単語を取出しテンプレートにセットする ポインタが指す文字の文字キューに単語を追加する 文字（アルファベット）順に以下の操作を行う カレントの文字の文字キューの中身を単語キューに追加する テンプレートのポインタを右に一つずらす

22 ここからは部品

23 クイックソートの動き ２２ ２７ ７ ２１ ２１ ４７ ６ １０ ３３ ランダムに基準値を選ぶ i と j がすれ違うまで繰り返す
基準値以上の値を検知する 基準値以下の値を検知する i と j がまだすれ違っていなければ A[i]とA[j]を交換する i と j を一歩進める 必要があれば部分問題を解く

24 クイックソートの動き ２２ ２７ 　７ ２１ ４７ 　６ １０ ３３

25 クイックソートの動き １０ 　６ 　７ １０ 　６ 　７ ２１ ４７ ２７ ２２ ３３ ４７ ２７ ２２ ３３ １０ 　６ 　７ ４７ ２７ ２２ ３３

26 クイックソートの動き １０ 　６ 　７ １０ 　６ 　７ ２１ ４７ ２７ ２２ ３３ ４７ ２７ ２２ ３３ 　６ １０ 　７ １０ 　７ ４７ ２７ ２２ ３３ １０ 　７

27 クイックソートの動き １０ 　６ 　７ １０ 　６ 　７ ２１ ４７ ２７ ２２ ３３ ４７ ２７ ２２ ３３ 　６ １０ 　７ １０ 　７ ４７ ２７ ２２ ３３ 　７ １０

28 クイックソートの動き １０ 　６ 　７ １０ 　６ 　７ ２１ ４７ ２７ ２２ ３３ ４７ ２７ ２２ ３３ 　６ １０ 　７ １０ 　７ ２２ ２７ ４７ ３３ ４７ ３３ 　７ １０ ４７ ３３

29 クイックソートの動き １０ 　６ 　７ １０ 　６ 　７ ２１ ２１ ４７ ２７ ２２ ３３ ４７ ２７ ２２ ３３ 　６ 　６ １０ 　７ ２２ ２２ ２７ ２７ ４７ ３３ 　７ 　７ １０ １０ ３３ ３３ ４７ ４７ 　６ 　７ １０ ２１ ２２ ２７ ３３ ４７