currently I have
type Example = (String,Int)
qsort:: [Example]->[Example]
qsort [] = []
qsort (x:xs) = qsort [y|y<-xs,y<=x] [x] qsort[y|y<-xs,y>x]
But this performs quick sort based on the first element of tuples:
qsort [("Alfie",55),("Scott",12),("Harry",82)] returns,
[("Alfie",55),("Harry",82),("Scott",12)]
CodePudding user response:
You can unpack the 2-tuples and filter on the value of the second item of the 2-tuple, so something like:
sort_dog_list :: [Dog]->[Dog]
sort_dog_list [] = []
sort_dog_list (x@(_, a):xs) = sort_dog_list [y|y@(_,ay) <-xs, … ] x : sort_dog_list[y|y@(_, ay) <- xs, … ]
Where I leave filling in the …
parts as an exercise.
CodePudding user response:
type Example = (String, Int)
merge :: [Example] -> [Example] -> [Example]
merge xs [] = xs
merge [] ys = ys
merge (x@(_,a):xs) (y@(_,b):ys) | a <= b = x:merge xs (y:ys)
| otherwise = y:merge (x:xs) ys
msort :: [Example] -> [Example]
msort [] = []
msort [x] = [x]
msort xs = merge (msort (firstHalf xs)) (msort (secondHalf xs))
firstHalf xs = let { n = length xs } in take (div n 2) xs
secondHalf xs = let { n = length xs } in drop (div n 2) xs
This is a custom merge sort for the Example
data type and sort based on the second element of the tuple.
merge
just merges 2 sorted lists of Example
s, looking at the second elements in the tuples, a
and b
.
firstHalf
and secondHalf
are the dividing functions.
msort
is the encompassing function that couples firstHalf
and secondHalf
with merge
.
Short test:
λ> msort [("Alfie",55),("Scott",12),("Harry",82)]
[("Scott",12),("Alfie",55),("Harry",82)]
Credits: This is the source I looked up the Haskell merge sort implementation from.