gistfile1.hs

-- Q1 Write a function to sort a list
  
  --Trying out bubble sort just to see how i would approach it in haskell
  --recursve sorts like quicksort would likely be more natural to express
  
  --helper function does one iteration of the bsort algorithm
  bsorthelper [] = []
  bsorthelper [a] = [a]
  bsorthelper lst = let
    (f:s:rest) = lst
    in if f < s
      then
        (f:bsorthelper (s:rest))
      else
        (s:bsorthelper (f:rest))

  --bsort function. So named not because of bubble sort's reputation, but rather because this implementation
  --always iterates over a list of length n, n times, thus even reducing bubble sorts decent performance
  --on nearly sorted lists. Didn't feel like keeping track of the status of the list in the helper
  --at the moment. May come back to this in future
  bsortstupid lst = last (take (length lst) (iterate bsorthelper lst))
  
  -- Quicksort implementation, it indeed feels much more natural than bsort.
  qsort [] = []
  qsort [a] = [a]
  qsort lst = let
    --take the middle element of the list as the pivot
    (f, s) = splitAt (floor (fromIntegral (length lst) / 2)) lst
    pivot = head s
    withoutpivot = f ++ (tail s)
    --gather the sublists
    left = [ el | el <- withoutpivot, el <= pivot ]
    right = [ el | el <- withoutpivot, el > pivot ]
    -- do the recursive call to quicksort in the return value
    in (qsort left) ++ [pivot] ++ (qsort right)