## DEV Community is a community of 643,323 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Quick Sort implemented in Erlang Analysis

Eric Douglas
A lover of wisdom 🧙🏽‍♂️ in a journey to master scalable software development.

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.

``````

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