CS 6.006 Lecture 7 Counting sort, radix sort, lower bounds for sortingを見る

CS 6.006 Lecture

トピック

  • Insertion Sort
  • Merge Sort
  • Heap Sort
  • Counting Sort
  • Radix Sort

わかったこと

Insertion, Merge, Heap Sortは要素同士の大小関係の判定(Comparison)を行うが、これを行なっている限り最低でもnlognの計算量がかかる。

理由

最低かかる計算量は、決定木の高さに等しい。 答えのパターンを葉としてもつ決定木を考える。 例えば、10個の要素がある配列のソートした時の答えとして、

A[0]<=A[1]<= ... <=A[9] とか

A[3]<=A[6]<=...A[2]

というパターンが考えられる。 (もちろん正しいのは一つのみ。)

とすると、答えのパターンは全部でn!通りあるので、決定木の木の高さはlog(n!)である。(底は2) 決定木の高さ=最低限必要な計算量なので、log(n!)の下限を求めることで、\Omega(nlogn)がわかる。

Counting SortはStableにソートすることができる。

今までの自分のCounting Sortの認識

a = [4, 2, 0, 3, 1, 3]をソートするとき。

  1. 各数字の出現数をメモしたいので、0, 1, 2, 3, 4の出現数を記録するための配列cntを作る。(長さは5になる) cnt = [0, 0, 0, 0, 0]

  2. aをスキャンして出現数をカウントする。 cnt = [1, 1, 1, 2, 1]

  3. cntをスキャンして、sorted_aに要素を入れる。

sorted_a = [0 for _ in range(len(a))]
target_ix = 0
for i in range(len(cnt)):
  value = i
  count = cnt[i]
  while count:
    sorted_a[target_ix] = i
    count -= 1
    target_ix += 1

問題点

Stableなソートができなくなる。Stableとは、ソートの前後で同じキーを持つ要素の順番が変わらないことを言う。 上の例では、キーはaに出て来る数字そのものとしたが、aが例えばHumanオブジェクトの配列で、身長順に並べたい時、 同じ身長のオブジェクトの順序が保証されなくなる。

Alice = Human(身長150, 体重40) Bob = Human(身長160, 体重50) Charlie = Human(身長150, 体重70) のとき、AliceとCharlieは同じ身長なので、順序はどちらでも良いと思うかもしれない、が、 常に出現した順を保ってソートしたいという状況がある。これを実現するのがStable Sortである。

[Alice, Charlie, Bob]であればStable Sort, [Charlie, Alice, Bob]の可能性があるならUnstable Sortである。

Counting Sort + Stable Sortを行うには？

上に書いた3.のステップをこのように書き換える。

3'. cntを直接スキャンする前に、前処理を加える。 cnt =「各数字の出現数」だが、各数字の、「その数字より小さい要素の個数」を表すように変形する。 cnt = [1, 1, 1, 2, 1]であれば、 cnt = [0, 1, 2, 3, 5]である。 ここで、それぞれの数字は、ソートされた配列に入るべきインデックスを表している 例えば、cntの4番目の要素cnt[4]は、5である。 これは、4という数字はソートされたら5番目にくる、ということを表している。

4'. aをスキャンし、cntを元に、sorted_aに要素を入れる。

sorted_a = [0 for _ in range(len(a))]
for num in a:
  target_ix = cnt[num]
  sorted_a[target_ix] = num
  cnt[num] += 1

ここで、最後の行でcnt[num] += 1しているのは、 もう一度同じ数字が出てきたときに、同じインデックス(target_ix)に入らずに、次のインデックスに入れるようにするためである。

このようにして、stableなソートが実現できる。

Counting Sortの計算量などは、動画で十分説明されているし、よくわかったので省略します。