Re: [請益] 快速排序的問題

[dryman (dryman)]

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
→ Favonia:忘了 [] 的 case... 然後用 partition 省 ++ 不一定有好處
忘了寫boundary condition orz
→ Favonia:看似 tail recursion 但 acc 還是有一堆 ++ 等著算 xDDDDD
這個嚴格來說不是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)
推 Favonia:我覺得你不能用其他程式語言的執行順序來理解 Haskell...
→ Favonia:前者 stack 大小的期望值和後者 acc 大小的期望值只差常數
→ Favonia:GHC 的預設實作中不會用到的部份根本不會算，這是重點。
→ dryman:哈，我其實比較熟的FP語言是scrict而不是lazy