Linear complexity selection algorithm (from Algo class at coursera).

LinearSelection.hs

module LinearSelection where

import System.Random (randomRIO)
import System.IO.Unsafe (unsafePerformIO)

select :: Ord a => [a] -> Int -> a
select [x] 1 = x
select xs n
  | n > length xs || n <= 0 = error $ "select: wrong index (" ++ show n ++ ") where length is " ++ show (length xs)
  | length ls < n = select bs (n - length ls)
  | otherwise = select ls n
  where (ls, bs) = partition xs

partition :: Ord a => [a] -> ([a], [a])
partition [] = ([], [])
partition xs = go ([], []) xs
  where pivot = xs !! (unsafePerformIO $ randomRIO (0, length xs - 1))
        go (ls, bs) (y:ys)
          | y > pivot = go (ls, y:bs) ys
          | otherwise = go (y:ls, bs) ys
        go ps [] = ps