是否有可能做一个列表只有一个通过快速排序？ [英] is it possible to do quicksort of a list with only one passing?

问题描述

  quickSort（x：xs）=（quickSort less）我学习haskell，我看到的函数定义是： ++（x：等于）++（quickSort more）
其中less = filter（< x）xs 
 equal = filter（== x）xs 
 more = filter（> x）xs 
  

是否可以只用一个遍历列表而不是3来编写它？

解决方案

虽然很晚，但这是一个应该不会泄漏空间的版本（而且似乎运行速度比其他3路版本快两倍）：

  qsort3 xs = go xs [] 
 where 
 go（x：xs）zs = part x xs zs [] [] [] 
 go [] zs = zs 
 part x [] zs abc = go a（（x：b ）+ + + + + + + + + + + + + + + + + + + + + + + + +部分x ys zs（y：a）b c 
 EQ  - >部分x ys zs a（y：b）c 
 GT  - >部分x ys zs ab（y：c）
  

这解决了使用元组的可能的问题， code> let（a，b）= ... 实际上被翻译成 let t = ...; a = fst t; b = snd t 这导致了即使在 a 被消费和处理之后，它仍然保持活着的状态，作为元组 t ，可以从中读取 b - 尽管当然完全没有必要。这被称为Wadler对空间泄漏问题。或者GHC（ -O2 ）比这更聪明。 :)

此外，这显然使用差异列表方法（谢谢，哈马尔），这也使得它更有效率（约两倍版本使用元组）。我认为部分使用累加器参数，因为它以相反的顺序构建它们。

I am learning haskell and the function definition I see is:

quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more)
                 where less = filter (< x) xs
                       equal = filter (== x) xs
                       more = filter (> x) xs

Is it possible to write it with only one traversal of the list, instead of 3?

解决方案

Although late, here's a version that's supposed to not leak space as much (and seems to run about twice faster than the other 3-way version here):

qsort3 xs = go xs [] 
  where
    go     (x:xs) zs       = part x xs zs [] [] []
    go     []     zs       = zs
    part x []     zs a b c = go a ((x : b) ++ go c zs)
    part x (y:ys) zs a b c =
        case compare y x of
                  LT -> part x ys zs (y:a) b c
                  EQ -> part x ys zs a (y:b) c
                  GT -> part x ys zs a b (y:c)

This addresses the possible problem with using tuples, where let (a,b) = ... is actually translated into let t= ...; a=fst t; b=snd t which leads to the situation where even after a has been consumed and processed, it is still kept around alive, as part of the tuple t, for b to be read from it - though of course completely unnecessary. This is known as "Wadler pair space leak" problem. Or maybe GHC (with -O2) is smarter than that. :)

Also this apparently uses difference lists approach (thanks, hammar) which also makes it a bit more efficient (about twice faster than the version using tuples). I think part uses accumulator parameters, as it builds them in reversed order.

这篇关于是否有可能做一个列表只有一个通过快速排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！