Можно ли сделать быструю сортировку списка только с одной передачей?

Question

Я изучаю haskell, и определение функции, которое я вижу:

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

Можно ли написать его только одним обходом списка вместо 3?

Answer 1

Ты имеешь в виду что-то подобное?

quicksort [] = []
quicksort (x:xs) = quicksort less ++ (x : equal) ++ quicksort more
  where (less, equal, more) = partition3 x xs

partition3 _ [] = ([], [], [])
partition3 x (y:ys) =
  case compare y x of
    LT -> (y:less, equal, more)
    EQ -> (less, y:equal, more)
    GT -> (less, equal, y:more)
  where (less, equal, more) = partition3 x ys

Обратите внимание, что на самом деле это не быстрая сортировка, так как реальная быстрая сортировка на месте.

Answer 2

Кажется, ничего не улучшается, кроме:

qs (x:xs) = let (a,b) = partition (< x) xs in (qs a) ++ [x] ++ (qs b)

Answer 3

Хотя и с опозданием, вот версия, которая должна не пропускать пространство так много (и, похоже, работает примерно в два раза быстрее, чем другая 3-сторонняя версия здесь):

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)

Это решает возможную проблему с использованием кортежей, где let (a,b) = ... фактически переводится в let t= ...; a=fst t; b=snd t, что приводит к ситуации, когда даже после того, как a был потреблен и обработан, он все еще остается живым как часть кортежа t, для b, чтобы быть прочитанным из этого - хотя конечно совершенно ненужный.Это известно как проблема «утечки пространства в паре Вадлера».Или, может быть, GHC (с -O2) умнее этого.:)

Также здесь, очевидно, используется подход списки различий (спасибо, hammar), что также делает его немного более эффективным (примерно в два раза быстрее, чем версия, использующая кортежи).Я думаю, что part использует параметры аккумулятора, поскольку строит их в обратном порядке.