module Weihnacht where
import Data.List(sort,sortBy)
import System.Random
import IOExts
mergeSort :: Ord a => [a] -> [a]
mergeSort [ ] = [ ]
mergeSort [x] = [x]
mergeSort xs = mergeSort a `merge` mergeSort b
where (a,b) = pair xs
pair (x:x':xs) = let (a,a') = pair xs in (x:a, x':a')
pair x = (x,[])
merge (x:xs) (y:ys) | x <= y = x : merge xs (y:ys)
| True = y : merge (x:xs) ys
merge x y = x ++ y
bubbleSort :: Ord a => [a] -> [a]
bubbleSort xs | xs == xs' = xs
| otherwise = bubbleSort xs'
where xs' = bubbleUp xs
bubbleUp (x1:x2:xs) = min x1 x2 : bubbleUp (max x2 x1 : xs)
bubbleUp xs = xs
lossySort :: Ord a => [a] -> [a]
lossySort (x:y:xs) = [min x y, max y x]
lossySort xs = xs
isSort1 :: Ord a => [a] -> Bool
isSort1 (x1:x2:xs) | x1 <= x2 = isSort1 (x2:xs)
| otherwise = False
isSort1 _ = True
isSort2 :: Ord a => [a] -> Bool
isSort2 xs = sort xs == xs
isSort3 :: Ord a => [a] -> Bool
isSort3 xs@(x:xs') = all id $ zipWith (<=) xs xs'
isSort3 _ = True
isSort4 :: Ord a => [a] -> Bool
isSort4 xs = [ (xs !! i, xs !! j) |
i <- [0 .. length xs - 2],
j <- [i + 1 .. length xs - 1],
xs !! i > xs !! j
] == []
shuffle :: [a] -> [a]
shuffle = sortBy rand
where rand x y = if fst . random $ unsafePerformIO newStdGen then LT else GT
randomSort :: Ord a => [a] -> [a]
randomSort = head . filter isSort . iterate shuffle
isSort :: Ord a => [a] -> Bool
isSort = isSort1