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]
Top comments (0)