2008/01/21

關鍵

又把 derivation of radix sort 看一遍,比較知道它在幹嘛了,關鍵仍然落在 stability 的條件上。在 paper 裡面,這個關鍵條件是 map (treesort ds) . ptn d = ptn d . treesort ds。左邊的意思是先用 most significant field 把 input lists 的元素分類(ptn d),然後對每一類用 less significant fields 排序;右邊的意思是先用 less significant fields 把整個 input list 排序過,再用 most significant field 分類。Gibbons 對這個條件的說明是:

Informally, this condition states that ptn d is stable: partitioning a sorted sequence yields a collection of sorted buckets.

讓我想想怎麼 "formally" 說明這件事 XD。

--
明天應該試著把整篇 paper 算一遍才對 XD。


好像的確那句 informal explanation 就夠了 XD。

Labels:

<< 回到主頁