アルゴリズムイントロダクション Chapter 8

線形時間ソーティング。比較ソートがnlognかかることの証明と、その結果を利用した別のアルゴリズムの計算量の下界の証明。obliviousなsort。

Exercise 8.1-1

n-1

Exercise 8.2-4

def exercise_8_2_4(a,k)
  n = a.length
  c = Array.new(k+1)
  for i in 0..k
    c[i] = 0;
  end
  for i in 0...n
    c[a[i]] += 1
  end
  for i in 1..k
    c[i] += c[i-1]
  end
  return lambda{|a,b|
    if a == 0
      c[b]
    else
      c[b] - c[a-1]
    end
  }
end

Exercise 8.3-2

insertion, merge
インデックスをそれぞれにメモして置いて、比較する際にインデックスの大小も見る。

Exercise 8.3-4

n進法でradixsortする

Exercise 8.4-2

insertion sort以外を使う

Exercise 8.4-3

Exercise 8.4-4 8.4-5

Pから乱数を引いてきてそれを分割に使う。よく出てくるところは分割が細かく、よく出てこないところは粗くなる。

Problem 8-2 e

stableにはできないようだ
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Radix/

Problem 8-4

b

状態木を考えると葉の数がn!個だからソートの時と同様にして示せる。

c

赤からpivotを一つ決めて、青をPartitionする。一つ同じ容量のものが見つかるのでそれをpivotとして赤をPartitionする。
pivot以下、以上についてこれを繰り返す。
赤と青がソートされるので、同じインデックスのものがペア

Problem 8-7

http://www.cs.dartmouth.edu/~cs110/Stupid%20Columnsort%20Tricks.pdf