アルゴリズムイントロダクション 8 章「線形時間ソーティング」
数学的基礎とデータ構造 (アルゴリズムイントロダクション)の 8章
8.1-1
3要素の決定木で分かるとおり、前提条件から比較せずとも大小関係を知る事が出来る場合がある。
lgn - 1 かな？自信ない。答えがないのはつらい。
8.1-2
分かりません。
8.1-3
分かりません。
8.2-1
ノートに描いた。
8.2-2
右にあるものから右側に配置されていくので安定。
8.2-3
上述の通り安定ではない。
8.2-4
counting-sort に使った size = k のカウントの和の配列を最初にとっておけば。
C(a) - C(b) みたいな感じで個数がとれる。
8.3-1
ノートに描いた。
8.3-2
挿入ソート、マージソート。
同じ値の要素の順番を記憶しておきソート後戻す。
8.3-3
n=1のときは明らかに成り立つ。
n=kのときになり立つとすると k + 1 桁目でソートすれば k + 1 でも成り立つ。
下位の順序を維持するために安定ソートである必要がある。
8.3-4
答えを見た。なるほどなあ。基数とは。
8.4-1
ノートに描いた。
8.4-2
O(n^2)。入力に片寄りがあり1つのバケツに入ってしまった場合。
改良するなら挿入ソートでなくクイックソートを使う。
