Sorting algorithm in Haskell

Question

I am trying to implement a very trivial sorting algorithm in Haskell. It compiles but keeps giving me incorrect outputs.

Here is the code

import Data.List

minimum' :: (Ord a) => [a] -> a
minimum' (x:xs) = foldr (\ x y -> if x <= y then x else y) x xs

qsrt :: (Ord a) => [a] -> [a]
qsrt [] = []
qsrt l@(x:xs) = minimum' l : qsrt xs

Any thoughts?

What leads you to believe that qsrt would sort the list? Which sorting algorithm are you trying to implement? — jub0bs
– jub0bs, Commented Jul 1, 2015 at 18:53
Well, I am only a novice. My thinking was, if I pattern match on (x:xs) extract the smallest element of that list and cons it with a recursion on the same function of the tail of the list I would eventually end up with a sorted list.. But the logic is clearly incorrect. None in particular. Just refactoring some functions myself for academic purposes. — Luis Dos Reis
– Luis Dos Reis, Commented Jul 1, 2015 at 18:55
qsrt takes the minimum element of l and then skips x, but x would only be the minimum element of l by accident so you're usually skipping the wrong element. — Rein Henrichs
– Rein Henrichs, Commented Jul 1, 2015 at 18:55
You're probably trying to implement selection sort. Try let qsrt [] = []; qsrt l = let y = minimum' l in y : qsrt (delete y l) — jub0bs
– jub0bs, Commented Jul 1, 2015 at 19:04

Rein Henrichs · Accepted Answer · 2015-07-01 19:03:38Z

6

The logic error is that qsrt takes the minimum element of l and then skips x, but x would only be the minimum element of l by accident so you're usually skipping the wrong element.

answered Jul 1, 2015 at 19:03

Rein Henrichs

15.7k1 gold badge47 silver badges55 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Luis Dos Reis · Accepted Answer · 2015-07-06 16:04:35Z

1

Just as an addendum to Rein Henrichs's answer, I managed to craft a correct version of the above using a filter.

import Data.List

minimum' :: (Ord a) => [a] -> a
minimum' (x:xs) = foldl' (\ x y -> if x <= y then x else y) x xs

srt :: (Ord a) => [a] -> [a]
srt [] = []
srt l = ml : srt (delete ml l)
    where ml = minimum' l

edited Jul 6, 2015 at 16:04

answered Jul 1, 2015 at 19:19

Luis Dos Reis

3931 gold badge3 silver badges17 bronze badges

2 Comments

Franky Over a year ago

This will give wrong results if the list contains duplicate elements.

Luis Dos Reis Over a year ago

@Franky Thanks for pointing it out. It should work as intended now.

Collectives™ on Stack Overflow

Sorting algorithm in Haskell

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related