クイックソート

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

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

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

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

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

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

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

クイックソートの平均時間計算量 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）時間

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

バケットソート

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

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

辞書式順序 単語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

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

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

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

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

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

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

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

ここからは部品

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

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

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

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

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

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

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