之前寫過一篇"[Algo] Radix Sort for general floating type",
討論data為浮點數時, Radix Sort的實作方式和效率分析

這篇是針對任意type討論,
並依序加入一些"合理"的限制以方便討論



Background Description

Sort Lower Bound:
    Sort的lower bound可以用comparing tree的概念去證明,
    建立在compare & exchange的運算模型下, 最快只能到Omega(NlgN),
    換句話說, 若想挑戰更低的極限, 必須跳出compare & exchange的模式

    但無論如何, 基於每筆data一定要存取到的原則,
    在Turing Machine架構下, Omega(N)是絕對的lower bound

Radix Sort [*1]:
    把data建立出多個key, 依據最不重要的key到最重要的key來做sort,
    運算是建立在hash上, 依據key存在有順序的陣列上,
    再依順序取回來, 即可達到排序 (沒有compare, 也沒有exchange)



假設有N筆data, 對應的key是整數型態, 無限定range,
這是很常見也很容易產生的一種key的type
( one data <-> one key )

因為沒有限定range, 必須考慮如何產生多種key,
使得key的range在限定範圍, 才能用陣列存

先排除負數的考量:
a. 依據key的正負值把data分成兩堆, theta(N)
b. 各別對正數, 負數兩堆key做Radix Sort
c. 把排好的兩堆key串在一起就完成sort了, theta(N)

排除負數的前置動作沒有使complexity超出theta(N)

以下的討論著眼在key value為0 ~ 正無窮大整數內

設有 N 筆 data, 陣列的index range為 0 ~ K
a. 將key視為 K 進位的值, 依K^0, K^1, ..., K^D拆為key0, key1, ..., keyD [*2]
b. 依key0, key1, ..., keyD的順序做Radix Sort,
   Complexity為 (N+K) * D

N, K都是可以決定的值, D的值依key的max value而有改變,
D = ceiling( log(max absolute value of key) ), log是以K為底數 [*3]

所以, 當max absolute value of key < K時,
效率為theta(N), 是個特例, 也是一般提到Bucket Sort時的情況

加上 N >= K的條件, 可以使comlexity更精確, 貼近一般的使用情況,
complexity = theta(N*D)

換句話說, 只有當D < logN時,
理論上Radix Sort才會比based on compare & exchange的sort快,
別忘了D的值也是log的結果, 取決於陣列的大小和key的max value

既然Radix Sort必須在特定條件下才能變快,
我覺得它並沒有很成功地跨越Omega(NlgN)的障礙, 感覺有點偷吃步

如果based on compare & exchange,
對sort的目標加上一些條件限制,
是否能得出一般化且跨越Omega(NlgN)的sort呢?
這樣的Algorithm, 是否能描述的出來呢? [*4]



PS

[1] Radix Sort Algorithm: (參考用的描述, 有條件限制的使用)
已知: 有n筆資料, 每個element有d個key, 這d個key的range在0~N-1之間
作法:

0. 準備一個一維陣列A, size是N, 假設實作方式用linked-list當陣列的type,
　 就是類似hash table的其中一種作法
1. 用第d個key, 把n筆資料都插到subscript為key(d)的地方,
   也就是A[key(d)].addLast(elem)
2. for i = 0 ~ N-1，把element都取回來
3. 按順序把key從d-1 ~ 0重覆step 1, 2

analysis:
time complexity
insert   ：d * n
retreive：d * N
total     ：O( d * (n+N) )

這裡的n+N有點模糊, 依實作方式也可以真的達到d*(n+N), 但這不影響order,
取K = max(n, N), 說它是O(d * 2K)也無所謂

[2]把key拆成key0 ~ keyD的作法
keyM = key mod K     # Radix Sort使用keyM
key = key / K

[3] ceiling(N)
ceiling(3.3) = 4
ceiling(3.0) = 3
ceiling(2.9) = 3

[4] 比方insertition Vs order"很正確"的data 
insertion sort的complexity為Omega(N), O(N^2),
不知在限定條件下加上機率運算, 能否算出一個明確的complexity?
這可能得看條件要怎麼限定了