Skip to content

Instantly share code, notes, and snippets.

@topher6345
Last active May 1, 2018 20:48
Show Gist options
  • Save topher6345/06144f14443551419864e101b3440c38 to your computer and use it in GitHub Desktop.
Save topher6345/06144f14443551419864e101b3440c38 to your computer and use it in GitHub Desktop.
Selection Sort in Haskell and Elixir
defmodule SelectionSort do
def sort(list), do: sort(list, [])
def sort([], result), do: result
def sort(list, result) do
min = minimum(list)
xs = delete(list, min)
sort(xs, result ++ [min])
end
def minimum([head|tail]), do: minimum(tail, head)
def minimum([], memo), do: memo
def minimum([head|tail], memo) do
minimum tail, (if head < memo, do: head, else: memo)
end
def delete(list, item), do: delete(list, item, [], true)
def delete([], _, rest, _), do: rest
def delete([head|tail], item, rest, flag) do
if flag && (head == item) do
delete(tail, item, rest, false)
else
delete(tail, item, rest ++ [head], flag)
end
end
end
module SelectionSort (sort) where
sort :: (Ord a, Num a) => [a] -> [a]
sort list = selectionSort' list []
where
selectionSort' [] result = result
selectionSort' list result = selectionSort' tail' (result ++ [min])
where
min = minimum list
tail' = delete list min
minimum (head:tail) = minimum' tail head
minimum' [] memo = memo
minimum' (head:tail) memo = minimum' tail $ if head < memo then head else memo
delete :: (Num a, Eq a) => [a] -> a -> [a]
delete list item = delete' list item [] True
where
delete' [] item rest flag = rest
delete' (head:tail) item rest flag =
if flag && (head == item) then
delete' tail item rest False
else
delete' tail item (rest ++ [head]) flag
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment