Geek Answers Handbook

How does quicksort work in Haskell?

On the Haskell website , here is an example quicksort implementation :

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

There is an explanation on the site, but I have a couple of questions that I did not see that were addressed ...

  • where is the actual comparison / swap made on two items for re-order? This is handled by the "Ord" type definition itself (ordered). So the type forces this condition to be ordered?
  • the "more" filter defines the elements "> = p" (vault), therefore, does not mean that we get an additional anchor point [p] in the resulting function list due to the "+ + [p] 'element?
+5
source share
4 answers

/, ? Ord () . , ?

Ord?

Ord , a a , >, < ==. .

, ?

- :

quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

, :

1 #: , .

2 #: , , head p, xs. p , xs, p ( lesser) p, xs, p p. , , , , (.. quicksort) lesser (, , p) greater ( , p). , , , 1 # .

, , , :

sortedlesser ++ p ++ sortedgreater

sortedlesser - , quicksort lesser sortedgreater - , quicksort greater.

... p ?

" " " >= p" (), , [p] - '++ [p]'?

, , . , xs p. p xs. xs p, . , .

+15
  • , () QS. - lesser greater, <, >= - Ord - a, - wasn 't, < >=.
  • , xs - p xs.

crappy ASCII :

                                qs [5, 5, 6, 3, 1]
                                          |
                         qs [3, 1]   ++  [5] ++ qs [5, 6]
                             |            |       |
                  qs [1] ++ [3] ++ qs []  |    qs [] ++ [5] ++ qs [6]
                             |            |       |
                           [1, 3]    ++  [5]  ++ [5, 6]
                             \            |        /
                              \-------------------/
                                        |
                                  [1, 3, 5, 5, 6]
+30

Note that you can write this even shorter and more efficient (since it partitionscans the source list only once) with

quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where (lesser, greater) = partition (< p) xs
+8
source

If you want only one line:

qsortOneLine s = case s of{[]->[];(x:xs)->qsortOneLine [y | y<-xs, y<x] ++ x : qsortOneLine [y | y<-xs, y>=x]}

If you need more advanced code:

qsort3 :: Ord a => [a] -> [a]
qsort3 x = qsort3' x []
qsort3' [] y     = y
qsort3' [x] y    = x:y
qsort3' (x:xs) y = part xs [] [x] []  
      where
         part [] l e g = qsort3' l (e ++ (qsort3' g y))
         part (z:zs) l e g 
             | z > x     = part zs l e (z:g) 
             | z < x     = part zs (z:l) e g 
             | otherwise = part zs l (z:e) g

http://en.literateprograms.org/Quicksort_(Haskell )

+2
source

More articles:


All Articles