Skip to content

Instantly share code, notes, and snippets.

@LOZORD
Last active August 29, 2015 14:12
Show Gist options
  • Select an option

  • Save LOZORD/7cb42ed55624bf99f137 to your computer and use it in GitHub Desktop.

Select an option

Save LOZORD/7cb42ed55624bf99f137 to your computer and use it in GitHub Desktop.
A quicksort implementation in Haskell
-- the middle integer item from a list
middle :: [Integer] -> Integer
middle list = list !! (fromIntegral midInd)
where midInd = length list `div` 2
-- the median of three integer values
-- thanks to Tony Jiang from HH Coding for the improved algo!
qMed3 :: Integer -> Integer -> Integer -> Integer
qMed3 a b c = min firstMax (max firstMin c)
where firstMax = max a b
firstMin = min a b
{- attempted to use quicksort to get the median 8|
--> this resulted in infinite recursion :'(
qsMed3 :: [Integer] -> Integer
qsMed3 list = if (length list == 3) then middle $ quicksort list else undefined
-}
quicksort :: [Integer] -> [Integer]
quicksort [] = []
quicksort list = (quicksort lesser) ++ pivots ++ (quicksort greater)
where pivotVal = qMed3 (head list) (middle list) (last list)
pivots = filter (\x -> x == pivotVal) list -- possible duplicates
lesser = filter (\x -> x < pivotVal) list
greater = filter (\x -> x > pivotVal) list
-- Now, test our implementation
main :: IO ()
main = do
print $ quicksort [3]
print $ quicksort [1,2]
print $ quicksort [1,2,3]
print $ quicksort [3,1,2]
print $ quicksort [5,3,4,2,1]
print $ quicksort $ reverse [1..10]
-- test for duplicates
print $ quicksort $ reverse $ [4..10] ++ [-5..12]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment