CODEWITHSUNDEEP
sortinghaskell
user8138142
user8138142

Reputation:

Haskell recursive sort function

I would like to implement a sort function in Haskell with these two functions:

smallest :: (Ord a) => [a] -> a
smallest [] = error "empty list"
smallest [x] = x
smallest (x:xs)
  | x < smallest xs = x
  | otherwise = smallest xs

insert :: Int -> [Int] -> [Int]
insert x [] = [x]
insert x (y:ys)
  | x <= y = x:y:ys
  | otherwise = y:insert x ys

My idea is to insert the smallest value at the right position with a recursion but as I am new to Haskell I got some problems on how to implement that.

Upvotes: 0

Views: 1253

Answers (1)

Gurkenglas
Gurkenglas

Reputation: 2317

smallest (x:xs)
  | x < smallest xs = x
  | otherwise = smallest xs

duplicates the number of smallest queries at each point in the list, blowing up exponentially. Instead:

smallest (x:xs) = min x (smallest xs)

, or even just smallest = minimum. Here are a few sorts I can see with your functions or similar ones:

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

This one will need smallest to give back the remaining list as well:

selectSmallest :: [Int] -> (Int, [Int])
selectSmallest (x:xs) = let (y, ys) = smallest xs in if x < y
  then (x, xs)
  else (y, x:ys)

selectionSorta [] = []
selectionSorta xs = let (y, ys) = smallest xs in
  y : selectionSorta ys

Upvotes: 2

Related Questions