## Programming Praxis – Two Bad Sorts

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.