Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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]
@CMCDragonkai

This comment has been minimized.

Copy link

CMCDragonkai commented Sep 11, 2014

Here's another bubblesort style that I think is faster:

defmodule BubbleSort do
    @doc """
        Reverse a list, when first parameter is a list
    """
    def reverse(list) when is_list(list) do
        reverse(list, [])
    end
    @doc """
        Shifts the top of the list to the bottom of the accumulator
    """
    def reverse([head|tail], accumulator) do
        reverse(tail, [head|accumulator])
    end
    @doc """
        Base case, when there are no more elements in the list, return the accumulated list
    """
    def reverse([], accumulator) do
        accumulator
    end
    @doc """
        Sorts a list of integers from lowest to highest
    """
    def sort(list) when is_list(list) do
        # passed will short circuit the algorithm
        sort(list, [], :passed)
    end
    @doc """
        Accepts a list containing at least 3 elements, an accumulator and disregards the status parameter, but only if the head > second. If so, then it sorts again with the first stacked on top of the tail as the new list, and second stacked on top of the accumulator as the new accumulator, passing a unpassed status
        passing instance (bubbling up the x): 
         v
        [xyzzzzzz]
          v
        [yxzzzzzz]
           v
        [yzxzzzzz]
        (left side of the v is the accumulated sorted instance for a single pass, right side of the v is the list to be sorted for this instance of a single pass)
        old list: [x | y | zzzz]
        old accumulator: [a]
        new list: [x | zzzz]
        new accumulator: [y | a]
        The accumulator is acting as the reverse of a sorted pass. As the sorting passes over the elements, it creates an accumulator holding the sorted elements in reverse. The reverse is just there for performance, since prepending is faster than appending in a linked list.
    """
    def sort([first|[second|tail]], accumulator, _status) when first > second do
        sort([first|tail], [second|accumulator], :unpassed)
    end
    @doc """
        Accepts a list containing at least 2 elements, an accumulator and any status. The head in this case can be either the last element in the array, or an element that is not greater than the second element.
        old list: [x | zzzz]
        old accumulator: [a]
        new list: [zzzz]
        new accumulator: [x | a]
        Because the head is not bigger than the second, then the head can be pushed onto the accumulator as it is now sorted in this **instance** of sorting. In this case, the status is also just passed on, as it does not know whether the pass has ended.
    """
    def sort([head|tail], accumulator, status) do
        sort(tail, [head|accumulator], status)
    end
    @doc """
        Accepts an empty list, an accumulator list, and an unpassed status
        It will sort again, but this time with the reversed accumulator as the list, and an empty accumulator with a passed status.
        This the part where passes over the list are restarted. Because the bubble sort needs to go back to beginning of the list and try bubbling again.
        If there are no elements that can be bubbled up, then :passed will not change to :unpassed, and will just go through `sort([head|tail], accumulator, status)`, which will forward the :passed, until there is no tail, and then it will go to `sort([], accumulator, :passed)`, which will return the reversed accumulator. In this pass instance, it is the last pass, and there will always be one last pass which will run and make sure there is no more bubbling required.
    """
    def sort([], accumulator, :unpassed) do
        sort(reverse(accumulator), [], :passed)
    end
    @doc """
        Accepts an empty list, an accumulator list, and a passed status.
        This is the base case, if there is no more elements to sort, return the reversed accumulator.
    """
    def sort([], accumulator, :passed) do
        reverse(accumulator)
    end
end
@ajuljulian

This comment has been minimized.

Copy link

ajuljulian commented Mar 1, 2018

Thanks for putting these together. I made a few changes to your insertion sort and came up with this. It seems to be working as well :)

defmodule Sort.Insertion do

    def sort(list) when is_list(list) and length(list) <= 1 do
        list
    end

    def sort(list) when is_list(list) do
        [last_elem | first_part_reversed] = Enum.reverse(list)
        insert(last_elem, sort(Enum.reverse(first_part_reversed)))
    end

    defp insert(e, []) do
        [e]
    end

    defp insert(e, [min|rest]) do
        cond do
            min >= e -> [e,min|rest]
            true -> [min|insert(e, rest)]
        end
    end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.