In today’s Programming Praxis exercise, our task is to implement two inefficient sorting algorithms. Let’s get started, shall we?
Some imports:
import Control.Arrow import System.Random import System.Random.Shuffle
Stoogesort is fairly bad at O(n^2.7).
stoogesort :: Ord a => [a] -> [a] stoogesort [] = [] stoogesort xs@(h:t) = f $ if last xs < h then last xs : init t ++ [h] else xs where f = if length xs > 2 then s first 2 . s second 1 . s first 2 else id s p n = uncurry (++) . p stoogesort . splitAt (div (n * length xs) 3)
Bogosort is more interesting. It has the potential of sorting a list in O(n). The chance of this happening, however, is pretty low. The resulting average performance is a terrible O(n*n!).
bogosort :: Ord a => [a] -> IO [a] bogosort [] = return [] bogosort xs = if and $ zipWith (<=) xs (tail xs) then return xs else bogosort . shuffle' xs (length xs) =<< newStdGen
Some tests to see if everything is working properly:
main :: IO () main = do print . (== [1..5]) =<< bogosort [3,1,5,4,2] print $ stoogesort [3,1,5,4,2] == [1..5]
Seems like it is. Having said that, never use either of these in practice.
Tags: Haskell, programming, praxis, kata, bonsai, code, sort, algorithm, bogosort, stoogesort
