Last active
August 29, 2015 14:12
-
-
Save LOZORD/7cb42ed55624bf99f137 to your computer and use it in GitHub Desktop.
A quicksort implementation in Haskell
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| -- 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