Naive Implementierung

Mit Listenbeschreibungen.

> qsort1                :: Ord a => [a] -> [a]
> qsort1 []             =  []
> qsort1 (a:x)          =  qsort1 [ b | b <- x, b <= a ]
>                       ++ a : qsort1 [ b | b <- x, b >  a ]

Nachteil: die Liste x wird zweimal durchlaufen. Mit partition.

> qsort2                :: Ord a => [a] -> [a]
> qsort2 []             =  []
> qsort2 (a:x)          =  qsort2 l ++ a : qsort2 r
>     where (l, r)      =  partition (>= a) x

Endrekursive Variante

> qsort3                :: Ord a => [a] -> [a]
> qsort3 []             =  []
> qsort3 [a]            =  [a]
> qsort3 (a:x)          =  partition [] [] x
>     where
>     partition l r []  =  qsort3 l ++ a : qsort3 r
>     partition l r (b:y)
>         | b <= a      =  partition (b:l) r y
>         | otherwise   =  partition l (b:r) y

Verwendung akkumulierender Parametern

Die Variante ist Paulson, ML for the working programmer entnommen. qsort4 ist zusaetzlich mit der Ordnungsrelation <= parametrisiert.

> qsort4                :: (a -> a -> Bool) -> [a] -> [a] -> [a]
> qsort4 (<=) []    y   =  y
> qsort4 (<=) [a]   y   =  a:y
> qsort4 (<=) (a:x) y   =  partition [] [] x
>     where
>     partition l r []  =  qsort4 (<=) l (a : qsort4 (<=) r y)
>     partition l r (b:y)
>         | b <= a      =  partition (b:l) r y
>         | otherwise   =  partition l (b:r) y

Stabile Variante

Die Variante geht auf Lennart Augustsson zurueck. Im wesentlichen wird die Funktionsdefinition "verdoppelt".

> qsort                 :: (a -> a -> Bool) -> [a] -> [a] -> [a]
> qsort (<=) []    y    =  y
> qsort (<=) [a]   y    =  a:y
> qsort (<=) (a:x) y    =  qpart (<=) a x [] [] y

qpart partitions and sorts the sublists. Note that l and r are in reverse order and must be sorted with an anti-stable sorting.

> qpart (<=) a [] l r y =  rqsort (<=) l (a : rqsort (<=) r y)
> qpart (<=) a (b:x) l r y
>     | a <= b          =  qpart (<=) a x l (b:r) y
>     | otherwise       =  qpart (<=) a x (b:l) r y

rqsort is as qsort but anti-stable, ie reverses equal elements.

> rqsort                :: (a -> a -> Bool) -> [a] -> [a] -> [a]
> rqsort (<=) []    y   =  y
> rqsort (<=) [a]   y   =  a:y
> rqsort (<=) (a:x) y   =  rqpart (<=) a x [] [] y

> rqpart (<=) a [] l r y=  qsort (<=) l (a : qsort (<=) r y)
> rqpart (<=) a (b:x) l r y
>     | b <= a          =  rqpart (<=) a x (b:l) r y
>     | otherwise       =  rqpart (<=) a x l (b:r) y