CODEWITHSUNDEEP
listsortinghaskellfunctional-programming
rozjni
rozjni

Reputation: 49

Haskell: Sort list

I am new to Haskell. Can I fix this recursive function to sort all the integers in the array? If yes, how should the code be?

isort [] = []
isort [x] = [x]
isort (x:y:xs) = if x <= y then 
                    x:isort (y:xs) 
                else 
                    y:isort (x:xs)

Input in current function

isort [4,3,2,1]

gives as output now

[3,2,1,4]

But it should be

[1,2,3,4]

Upvotes: 1

Views: 1751

Answers (2)

rozjni
rozjni

Reputation: 49

Sort and insert one element in array

insert x [] = [x]
insert i (x:xs) = if i<=x then
                    i:x:xs
                else 
                    x:insert i xs

Loop insert function on the whole array

isort [] = []
isort (x:xs) = insert x (isort xs)

Upvotes: 0

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476557

Probably the smallest change to the code to let this sort a list is each time selecting the mymin of the list and yield this as first item of the result and recurse on the list, so:

mymin :: Ord a => [a] -> (a, [a])
mymin [x] = (x, [])
mymin (x:xs)
    | x <= y = (x, xs)  -- select a new minimum
    | otherwise = (y, x:ys)   -- use the minimum of the tail of the list
    where ~(y, ys) = mymin xs

then we can work with:

isort :: Ord a => [a] -> [a]
isort [] = []
isort xs = y : isort ys
    where (y, ys) = mymin xs

This is an implementation of selection sort [wiki] and thus runs in O(n2). I leave it as an exercise to implement faster algorithms like merge sort and Timsort.

Upvotes: 3

Related Questions