DEV Community

Eric Douglas
Eric Douglas

Posted on

Quick Sort implemented in Erlang Analysis

When you want to truly understand what you are studying, you must go all the way down in the rabbit hole in order to absorb the content.

This is a step by step analysis of what is happening in a quick sort algorithm implemented in the book Learn you Some Erlang for Great Good [1].

recursive.erl

-module(recursive).

-export([partition/4, quick_sort/1]).

quick_sort([]) -> [];
quick_sort([Pivot | Rest]) ->
    {Smaller, Larger} = partition(Pivot, Rest, [], []),
    quick_sort(Smaller) ++ [Pivot] ++ quick_sort(Larger).

partition(_, [], Smaller, Larger) -> {Smaller, Larger};
partition(Pivot, [H | T], Smaller, Larger) ->
    if H =< Pivot ->
           partition(Pivot, T, [H | Smaller], Larger);
       H > Pivot -> partition(Pivot, T, Smaller, [H | Larger])
    end.

Enter fullscreen mode Exit fullscreen mode

Analysis

quick_sort([5, 2, 2, 7, 6, 3])
  Pivot = 5
  Rest = [2, 2, 7, 6, 3]
  {Smaller, Larger} = ???

  partition(5, [2, 2, 7, 6, 3], [], [])
    Pivot = 5
    H = 2
    T = [2, 7, 6, 3]
    Smaller = []
    Larger = []

    partition(5, [2, 7, 6, 3], [2, []], [])
      Pivot = 5
      H = 2
      T = [7, 6, 3]
      Smaller = [2, []]
      Larger = []

      partition(5, [7, 6, 3], [2, [2, []]], [])
        Pivot = 5
        H = 7
        T = [6, 3]
        Smaller = [2, [2, []]]
        Larger = []

        partition(5, [6, 3], [2, [2, []]], [7, []])
          Pivot = 5
          H = 6
          T = [3]
          Smaller = [2, [2, []]]
          Larger = [7, []]

          partition(5, [3], [2, [2, []]], [6, [7, []]])
            Pivot = 5
            H = 3
            T = []
            Smaller = [2, [2, []]]
            Larger = [6, [7, []]]

            partition(5, [], [3, [2, [2, []]]], [6, [7, []]])
              Smaller = [3, [2, [2, []]]]
              Larger = [6, [7, []]]

  {Smaller, Larger} = {[3, [2, [2, []]]], [6, [7, []]]}

  %% (1) quick_sort([3, [2, [2, []]]] = Smaller) ++ [5 = Pivot] ++ (2) quick_sort([6, [7, []]] = Larger)
  quick_sort([3, 2, 2]) ++ [5] ++ quick_sort([6, 7])

  %% Solving (1) until the end
  quick_sort([3, 2, 2]) = quick_sort([2, 2]) ++ [3] ++ quick_sort([])
    quick_sort([2, 2]) = quick_sort([2]) ++ [2] ++ quick_sort([])
      quick_sort([2]) = quick_sort([]) ++ [2] ++ quick_sort([])

  %% Solving (2) until the end
  quick_sort([6, 7]) = quick_sort([]) ++ [6] ++ quick_sort([7])
    quick_sort([7]) = quick_sort([]) ++ [7] ++ quick_sort([])

  %% Replacing the values from our first quick_sort run
  %% obs 1: quick_sort([]) == []
  %% obs 2: consider that some values are from the left side quick_sort and other from righ side quick_sort

  %% quick_sort([3, 2, 2]) ++ [5] ++ quick_sort([6, 7])
  [2] ++ [2] ++ [3] ++ [5] ++ [6] ++ [7]

  %% Result
  [2, 2, 3, 5, 6, 7]
Enter fullscreen mode Exit fullscreen mode

References

  1. Book LYSE - chapter: Recursion

Top comments (0)