I am trying to implement bubble sort to sort my list by priority. For example, the list is of the following format with the 3rd element being priority:
[("Ted", 100, 3), ("Boris", 100, 1), ("Sam", 100, 2)]
I have tried the standard bubble sort method below, however this did not work. Any suggestions would be appreciated.
bubbleSort :: (Ord t) => [t] -> [t]
bubbleSort a = loop (length a) bubble a
bubble :: (Ord t) => [t] -> [t]
bubble (a:b:c) | a < b = a : bubble (b:c)
| otherwise = b : bubble (a:c)
bubble (a:[]) = [a]
bubble [] = []
loop :: (Num a, Ord a) => a -> (t -> t) -> t -> t
loop num f x | num > 0 = loop (num-1) f x'
| otherwise = x
where x' = f x
As hinted by luqui, it is normal to implement not the Ord constrained version of a sorting algorithm directly, but a more general one that uses a custom comparison:
bubbleSortBy :: (t->t->Ordering) -> [t] -> [t]
bubbleSortBy cmp a = loop (length a) bubble a
where
bubble :: (Ord t) => [t] -> [t]
bubble (a:b:c) = case cmp a b of
LT -> a : bubble (b:c)
_ -> b : bubble (a:c)
bubble l = l
loop :: Integral a -- (Num, Ord) is a bit /too/ general here, though it works.
=> a -> (t -> t) -> t -> t
loop num f x | num > 0 = loop (num-1) f x'
| otherwise = x
where x' = f x
the Ord version follows trivially from this:
bubbleSort :: (Ord t) -> [t] -> [t]
bubbleSort = bubbleSortBy compare
but often is more practical to use general version directly, like in your case
import Data.Function(on)
sorted_priority3rd = bubbleSortBy ( compare `on` \(a,b,c) -> (c,a,b) )
What this does is, it changes the order of arguments before each comparison. Obviously, this makes the bubble sort even slower; normally you'd rather do
import Data.List (sortBy) -- this is a proper 𝑂(𝑛 log 𝑛) sorting algorithm
sorted_by3rd = sortBy ( compare `on` \(a,b,c) -> c )
and care about the finer order later.