sort list of tuples without sortBy-CodePudding

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 Examples, 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.