Skip to content

Instantly share code, notes, and snippets.

@kevgathuku
Forked from rylev/sort.ex
Created June 18, 2018 10:37
Show Gist options
  • Save kevgathuku/af5640cfba49ba0e91eb738153ecec3c to your computer and use it in GitHub Desktop.
Save kevgathuku/af5640cfba49ba0e91eb738153ecec3c to your computer and use it in GitHub Desktop.
Sort Algorithms in Elixir
## Sort Algorithms in Elixir
# Selection Sort
defmodule Selection do
def sort(list) when is_list(list) do
do_selection(list, [])
end
def do_selection([head|[]], acc) do
acc ++ [head]
end
def do_selection(list, acc) do
min = min(list)
do_selection(:lists.delete(min, list), acc ++ [min])
end
defp min([first|[second|[]]]) do
smaller(first, second)
end
defp min([first|[second|tail]]) do
min([smaller(first, second)|tail])
end
defp smaller(e1, e2) do
if e1 <= e2 do e1 else e2 end
end
end
IO.inspect Selection.sort([100,4,10,6,9,3]) #=> [1, 3, 4, 6, 9, 10]
# Insertion Sort
defmodule Insertion do
def sort(list) when is_list(list) do
do_sort([], list)
end
def do_sort(_sorted_list = [], _unsorted_list = [head|tail]) do
do_sort([head], tail)
end
def do_sort(sorted_list, _unsorted_list = [head|tail]) do
insert(head, sorted_list) |> do_sort(tail)
end
def do_sort(sorted_list, _unsorted_list = []) do
sorted_list
end
def insert(elem, _sorted_list = []) do
[elem]
end
def insert(elem, sorted_list) do
[min|rest] = sorted_list
if min >= elem do [elem|[min|rest]] else [min|insert(elem, rest)] end
end
end
IO.inspect Insertion.sort([1, 2, 100, 3, 4, 1, 200, 45, 6, 10]) #=> [1, 1, 2, 3, 4, 6, 10, 45, 100, 200]
# Bubble Sort
defmodule Bubble do
def sort(list) when is_list(list) do
make_pass(do_sort(list, []), list)
end
def make_pass(bubbled_list, old_list) when bubbled_list != old_list do
do_sort(bubbled_list, []) |> make_pass(bubbled_list)
end
def make_pass(bubbled_list, old_list) when bubbled_list == old_list do
bubbled_list
end
def do_sort(_list = [], _acc) do
[]
end
def do_sort([first|[]], acc) do
acc ++ [first]
end
def do_sort([first|[second|tail]], acc) do
[new_first, new_second] = swap(first, second)
do_sort([new_second|tail], acc ++ [new_first])
end
defp swap(e1, e2) do
if e1 <= e2 do [e1, e2] else [e2, e1] end
end
end
IO.inspect Bubble.sort([1, 2, 100, 3, 4, 1, 200, 45, 6, 10]) #=> [1, 1, 2, 3, 4, 6, 10, 45, 100, 200]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment