Quicksort算法仅适用于小数字的列表.为什么？

Question

我添加了两个帮助功能来分割列表和添加tupples.输出有两个不同的列表作为输入显示我的问题.

*Main> quicksort [367,324,675,238,1237,345,12,45,1,434,2,1,33,43] [1,1,2,12,33,43,45,238,324,345,367,434,675,1237] - 它的工作原理

*Main> quicksort [3687,324,675,238,1237,345,12,45,1,434,2,1,33,43] [3687,324,675,238,1237,345,12,45,1,434,2,1,33,43] - 不起作用

下面是代码:

    splitBy :: Int -> [Int] -> ([Int],[Int])

    splitBy n y = ([x|x <- y,x > n],[x|x <- y, x<=n]) 
    addi :: ([a],[a]) -> ([a],[a]) -> ([a],[a])
    addi ([],[]) ([],[]) = ([],[])
    addi (x,y) (w,z) =  (x++w,y++z)

    splitBy' :: Int -> [Int] -> ([Int],[Int])

    splitBy' _ [] = ([],[])
    splitBy' n (y:ys) =  addi (q,d) (splitBy' n ys)
        where q = if y > n then [] else [y]
            d = if y <= n then [] else [y]
    addi' :: ([a],[a]) -> [a]
    addi' ([],[]) = []
    addi' (x,z) = x++z
    quicksort :: [Int] -> [Int]
    quicksort [] = []
    quicksort (x:xs) 
        | (l1 /= []    ) && (l2 /= []) = addi'(quicksort l1', quicksort l2')
        | l1 == [] = addi' (l1, quicksort l2)
        | l2 == [] = addi' (l1,l2)
            where
                (l1,l2) = splitBy' x (x:xs)
                (l1',l2') =  (addi'(splitBy' (x-1) l1),addi' (splitBy' (x+1) l2))

Answer 1

调试这样的代码时,QuickCheck是一个非常有用的工具.

我把你的代码放入Test.hs,加载ghci,然后运行:

*Test> import Test.QuickCheck
*Test Test.QuickCheck> quickCheck $ \xs -> quicksort xs == Data.List.sort xs
*** Failed! Falsifiable (after 8 tests and 5 shrinks):    
[1,0]
*Test Test.QuickCheck> quicksort [1,0]
[1,0]

现在,您有一个非常小的input([1,0])来查看和跟踪代码:

  quicksort (1::0::[]) -- has (l1,l2) = splitBy' 1 [1,0] = ([1,0],[])
= addi' ([1,0], [])       -- because  `l2 == []`
= [1,0] ++ []
= [1,0]

据推测,您对其中任何一种splitBy'或您的检查都有不同的行为quicksort.检查此执行与您的意图的不同之处,您将找到如何修复代码.