In yesterday’s Programming Praxis problem we have to implement two sort algorithms. Let’s get started.
First, some imports:
import Control.Monad import Data.List import Data.List.HT import Data.Array.IO import Data.Array.MArray
For the Comb sort algorithm, we’re going to need a function to swap two elements of an array.
swap :: (MArray a e m, Ix i, Ord e) => i -> i -> a i e -> m () swap i j a = do x <- readArray a i y <- readArray a j when (y < x) $ writeArray a i y >> writeArray a j x
The Comb sort algorithm itself:
combSort :: Ord a => [a] -> IO [a] combSort [] = return [] combSort xs = comb (s-1) =<< newListArray (1, s) xs where comb :: Ord a => Int -> IOArray Int a -> IO [a] comb 0 a = getElems a comb n a = mapM_ (\i -> swap i (i+n) a) [1..s-n] >> comb (n-1) a s = length xs
We don’t need array access for the Shell sort algorithm, so that saves some code. It’s in the IO monad so we can use the same test function, but the algorithm itself is pure.
shellSort :: Ord a => [a] -> IO [a] shellSort [] = return [] shellSort xs = return $ shell (last . takeWhile (< length xs) $ iterate (succ . (*3)) 1) xs where shell 1 = foldr insert [] shell n = shell (div (n-1) 3) . concatMap (shell 1) . sliceHorizontal n
A little test harness to see of everything’s working:
test :: ([Int] -> IO [Int]) -> IO () test f = do print . null =<< f [] print . (== [1..9]) =<< f [4,7,3,9,1,5,2,6,8] main :: IO () main = do test combSort test shellSort
Looks like it is.