25 Feb 06:13 2013

## Tournament knock out

Xinyu LIU <liuxinyu95 <at> gmail.com>

2013-02-25 05:13:08 GMT

2013-02-25 05:13:08 GMT

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:

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

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.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe <at> haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe