Sort Algorithms in Elixir

sort.ex

## 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]

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

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

https://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort#Elixir

defmodule Sort do
  def bsort(list) when is_list(list) do
    t = bsort_iter(list)
 
    if t == list, do: t, else: bsort(t)
  end
 
  def bsort_iter([x, y | t]) when x > y, do: [y | bsort_iter([x | t])]
  def bsort_iter([x, y | t]), do: [x | bsort_iter([y | t])]
  def bsort_iter(list), do: list
end

https://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort#Elixir

defmodule Sort do
  def bsort(list) when is_list(list) do
    t = bsort_iter(list)
 
    if t == list, do: t, else: bsort(t)
  end
 
  def bsort_iter([x, y | t]) when x > y, do: [y | bsort_iter([x | t])]
  def bsort_iter([x, y | t]), do: [x | bsort_iter([y | t])]
  def bsort_iter(list), do: list
end

Nice approach, I would avoid the if..

defmodule Sort do
  def bsort(list) when is_list(list) do
   t = bsort_iter(list)

   (t == list)
   |> maybe_sort_again(t)

  end

  def bsort_iter([x, y | t]) when x > y, do: [y | bsort_iter([x | t])]
  def bsort_iter([x, y | t]), do: [x | bsort_iter([y | t])]
  def bsort_iter(list), do: list

  def maybe_sort_again(false, list), do: bsort(list)
  def maybe_sort_again(true, list), do: list
end

Hello @ajuljulian cool stuff.

I made a minor change (pattern matching) to your solution

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]) when min >= e do
    [e, min | rest]
  end

  defp insert(e, [min | rest]) do
    [min | insert(e, rest)]
  end
end

dbg(Sort.Insertion.sort([4, 300, 42, 1, 10]))