This post is a followup to my previous post, about the median-of-median algorithm for selecting the \(i\)-th smallest element from an unsorted list of \(n\) elements. I had originally planned on including a Haskell implementation of the algorithm in that post, but, in order to increase the appeal of that post (Haskell is somewhat of a niche language), I decided to stick to a description of the algorithm and a theoretical analysis. This post is an implementation of the median-of-medians algorithm in literate Haskell.
For details about the median-of-medians algorithm, refer to my previous post. Here we will only outline the algorithm for convenient reference.
We begin first by implementing step 2.
> import Control.Arrow ((&&&)) > > import Data.List ((!!), partition, sort) > import Data.List.Split (chunksOf) > > indexOfMedian :: Int -> Int > indexOfMedian n = (n - 1) `div` 2 > > bruteForceMedian :: (Ord a) => [a] -> a > bruteForceMedian xs = (sort xs) !! (indexOfMedian $ length xs)
We now implement step 4.
> pivot :: (Ord a) => a -> [a] -> ([a], [a]) > pivot x = filter (< x) &&& filter (> x)
We now use these two functions to implement the median-of-medians algorithm.
> select :: (Ord a, Show a) => Int -> [a] -> a > select 0 [x] = x > select i xs > | i < k = select i smaller > | i == k = x > | otherwise = select (i - k - 1) larger > where medians = map bruteForceMedian $ chunksOf 5 xs > x = select (indexOfMedian $ length medians) medians > (smaller, larger) = pivot x xs > k = length smaller
We now write a simple test to validate
> testSelect :: Bool > testSelect = [1..100] == map (flip select (reverse [1..100])) [0..99]
This post is available as a literate Haskell file.