-- | Chapter 2

module IA3H.Chap2 (
  insertSort, selectionSort, mergeSort, bubbleSort
  ) where

-- | 2.1 Insertion sort
insert [] e = [e]
insert arr@(a:as) e = if e > a
                    then a : insert as e
                    else e : arr

insertSort a = foldl insert [] a

-- | 2.2 Analyzing algorithms
removeMax (e:[]) = (e, [])
removeMax (e1:e2:es) = let (m1, m2) = if e1 > e2 then (e1, e2) else (e2, e1)
                           (m, l) = removeMax (m2:es)
                       in if m1 > m then (m1, m:l) else (m, m1:l)

selectionSort lst = sortLoop [] lst
  where sortLoop s [] = s
        sortLoop s l = let (m, l') = removeMax l
                       in sortLoop (m:s) l'

-- | 2.3 Designing algorithms
merge [] r = r
merge l [] = l
merge l@(l1:ls) r@(r1:rs)
  | l1 <= r1 = l1 : merge ls r
  | otherwise = r1 : merge l rs

mergeSort lst = mergeSort1 lst (length lst)
  where mergeSort1 lst len
          | len <= 1 = lst
          | otherwise =
              let q = len `div` 2
                  (l, r) = splitAt q lst
              in merge (mergeSort1 l q) (mergeSort1 r (len - q))

-- | Problem 2-2 Correctness of bubblesort
bubble l [e] = (l, e)
bubble l (e1:e2:es)
  | e1 <= e2 = bubble (e1:l) (e2:es)
  | otherwise = bubble (e2:l) (e1:es)

bubbleSort lst = sortLoop [] lst
  where sortLoop s [] = s
        sortLoop s l = let (l', m) = bubble [] l
                       in sortLoop (m:s) l'
