Last active
May 1, 2018 20:48
-
-
Save topher6345/06144f14443551419864e101b3440c38 to your computer and use it in GitHub Desktop.
Selection Sort in Haskell and Elixir
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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