[Haskell-cafe] Tournament knock out
Xinyu LIU
liuxinyu95 at gmail.com
Mon Feb 25 06:13:08 CET 2013
Hi,
Tournament knock out is explained in [1] by Knuth. The limitation is that
it can only handle the sequence of the length 2^m for some integer m. When
the champion element is removed, it was replaced with negative infinity.
Typically negative infinity is represented by a predefined big negative
number.
Although heap sort solves all these limitation, I found tournament knock
out itself can work out.
Here is the Haskell code:
data Infinite a = NegInf | Only a | Inf deriving (Eq, Show, Ord)
only (Only x) = x
data Tr a = Empty | Br (Tr a) a (Tr a) deriving Show
key (Br _ k _ ) = k
wrap x = Br Empty (Only x) Empty
branch t1 t2 = Br t1 (min (key t1) (key t2)) t2
fromList :: (Ord a) => [a] -> Tr (Infinite a)
fromList = build . (map wrap) where
build [] = Empty
build [t] = t
build ts = build $ pair ts
pair (t1:t2:ts) = (branch t1 t2):pair ts
pair ts = ts
pop (Br Empty _ Empty) = Br Empty Inf Empty
pop (Br l k r) | k == key l = let l' = pop l in Br l' (min (key l') (key r)) r
| k == key r = let r' = pop r in Br l (min (key l) (key r')) r'
top = only . key
tsort :: (Ord a) => [a] -> [a]
tsort = sort' . fromList where
sort' Empty = []
sort' (Br _ Inf _) = []
sort' t = (top t) : (sort' $ pop t)
The detailed explanation can be found at:
https://github.com/liuxinyu95/AlgoXY/blob/algoxy/preview/ssort-en.pdf?raw=true
[1]. Donald E. Knuth. The art of computer programming, Volume 3, sorting
and searching.
Larry, LIU Xinyu
https://sites.google.com/site/algoxy/
https://github.com/liuxinyu95/AlgoXY
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130225/24d1f349/attachment-0001.htm>
More information about the Haskell-Cafe
mailing list