アルゴリズムイントロダクション 7 章「クイックソート」
数学的基礎とデータ構造 (アルゴリズムイントロダクション)の 7章
7.1-1
ノートに描いた。
7.1-2
r が返る。
(r + p)/2が返るようにするにはどうしたら良いだろう。
答えが見つからない。
7.1-3
n - 1回の比較が起きる。
7.1-4
比較を逆にすれば良い。
7.2-1
略。
7.2-2
Partition が 1 で終わるので O(n)
7.2-3
A[r] が最小の値になってしまうので分割が偏り n^2 。
7.2-4
ほとんどソートされている場合は比較の回数が少ない挿入ソートの方が有利。
7.2-5
最小の深さは常にαで分割された場合であるのは明らか。同様に最大は 1-α。
求める深さを k とすると最小の分割数 1 になるには n * α^k = 1 のとき
両辺の lg をとれば k = -lgn/lgα となる。
7.3-1
偏った最悪時ではなく平均を知りたいから。
