作者dryman (dryman)
看板CSSE
標題Re: [請益] 快速排序的問題
時間Tue Apr 17 15:12:19 2012
yauhh大寫的方法還蠻清楚的
提供一個有用accumulator來減少++的版本：
qsort [] acc = acc
qsort [x] acc = x:acc -- one element case
qsort (x:xs) acc = partition xs [] [x] []
where
partition [] less equal greater = qsort less (equal ++ (qsort greater acc))
partition (y:ys) less equal greater
| y > x = partition ys less equal (y:greater)
| y < x = partition ys (y:less) equal greater
| otherwise = partition ys less (y:equal) greater
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.109.22.88
1F：→ Favonia:忘了 [] 的 case... 然後用 partition 省 ++ 不一定有好處 04/17 21:20
忘了寫boundary condition orz
2F：→ Favonia:看似 tail recursion 但 acc 還是有一堆 ++ 等著算 xDDDDD 04/17 21:21
這個嚴格來說不是tail recursion，因為還是得暫存less的值
只是隨著執行時間它的stack會小於N（因為被推到ACC裡面去了）
而用++的stack會一直差不多等於N
※ 編輯: dryman 來自: 220.136.176.35 (04/17 21:32)
※ 編輯: dryman 來自: 220.136.176.35 (04/17 21:39)
3F：推 Favonia:我覺得你不能用其他程式語言的執行順序來理解 Haskell... 04/17 21:45
4F：→ Favonia:前者 stack 大小的期望值和後者 acc 大小的期望值只差常數 04/17 21:48
5F：→ Favonia:GHC 的預設實作中不會用到的部份根本不會算，這是重點。 04/17 21:49
6F：→ dryman:哈，我其實比較熟的FP語言是scrict而不是lazy 04/18 08:48