Skip to content

Instantly share code, notes, and snippets.

@WillNess

WillNess/quicksort3.hs

Last active February 10, 2016 13:49
Show Gist options
  • Save WillNess/4747361 to your computer and use it in GitHub Desktop.
Save WillNess/4747361 to your computer and use it in GitHub Desktop.
Download ZIP
quicksort3
Raw
quicksort3.hs
quicksort3 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)
quicksort4 xs = go xs [] where
go (x:xs) zs = part x xs zs id (x:) id
go [] zs = zs
part x [] zs a b c = go (a []) (b $ go (c []) zs)
part x (y:ys) zs a b c =
case compare y x of
LT -> part x ys zs (a.(y:)) b c
EQ -> part x ys zs a (b.(y:)) c
GT -> part x ys zs a b (c.(y:))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment