-- Sortierverfahren, zunächst für ganze Zahlen

-- a) Sortieren durch Einfügen - Insertion sort

iSort :: [Int] -> [Int] 
iSort [] = []
iSort (x:xs) = insert x (iSort xs)

insert :: Int -> [Int] -> [Int] 
insert x [] = [x]
insert x (y:ys) 
	| x <= y    = x:y:ys
	| otherwise = y : insert x ys

-- b) Sortieren durch Mischen - Merge sort

mSort :: [Int] -> [Int] 
mSort [] = []
mSort [x] = [x]
mSort xs = merge (mSort (take n xs)) (mSort (drop n xs))
           where n = length xs `div` 2

merge :: [Int] -> [Int] -> [Int]
merge [] xs = xs
merge xs [] = xs
merge (x:xs) (y:ys) 
	| x <= y    = x : merge xs (y:ys)
	| otherwise = y : merge (x:xs) ys

-- c) Sortieren nach Tony Hoare - Quick Sort

qSort :: [Int] -> [Int] 
qSort [] = []
qSort (x:xs) = qSort [ y | y <- xs, y <= x ] ++ [x] ++
               qSort [ y | y <- xs, y >  x ]

-- Testen von Sortierverfahren

-- a) Vereinbare einige Testlisten l1 bis l7
l1,l2,l3,l4,l5, l6, l7 :: [Int]
l1 = []
l2 = [-5]
l3 = [-2,5,76,-6,-4,3]
l4 = [1,2,3,4,5,6,7,8,9]
l5 = [9,8,7,6,5,4,3,2,1]
l6 = [1..1000]
l7 = [1000, 999..1]

-- b) Generiere Zufallszahlen

nextRand :: Int -> Int
nextRand n = (factor * n + inc) `mod` modulus

randomSequence  :: [Int]
randomSequence = iterate nextRand seed -- iterate :: (a -> a) -> a -> [a] aus Prelude

seed, factor, inc, modulus :: Int
seed = 17489
factor = 25173
inc = 13849
modulus = 65536

rN :: Int -> [Int] -- rN n ist eine Liste mit n Zufallszahlen
rN n = take n randomSequence