Quicksort on any type of list | Haskell

dumbQuestions 0
Viewed 88

I am currently learning Haskell on learnyouahaskell.com and they present us with the following quicksort algorithm for integer lists.

quicksort :: (Ord a) => [a] -> [a]    
quicksort [] = []    
quicksort (x:xs) =     
    let smallerSorted = quicksort (filter (<=x) xs)  
        biggerSorted = quicksort (filter (>x) xs)   
    in  smallerSorted ++ [x] ++ biggerSorted

Is there a way to modify it to accept any type of list? I was thinking of adding an extra parameter to indicate the the comparison operation to use

quicksort haskell sorting
1 Answers

You can, as you specify in your comment, pass a function that will determine if for example the first item is less than or equal the second item, or any other order relation.

In that case you thus can work with:

quicksort :: (a -> a -> Bool) -> [a] -> [a]    
quicksort _ [] = []
quicksort lte (x:xs) =
    let smallerSorted = quicksort lte (filter (`lte` x) xs)  
        biggerSorted = quicksort lte (filter … xs)
    in  smallerSorted ++ x : biggerSorted

For the … part, you will have to negate the lte function. I leave that as an exercise.

Willem Van Onsem0
Related