qsort.erl

% **Quicksort**
% The head of the list is taken as the pivot; the list is then split according to those elements smaller
% than the pivot and the rest. These two lists are then recursively sorted by quicksort, and joined together,
% with the pivot between them.

-module(test).
-export([qsort/1]).
         
reverse(List) ->
  reverse(List, []).

reverse([], Acc) ->
  Acc;
reverse([Head|Tail], Acc) ->
  reverse(Tail, [Head|Acc]).

divide_to_lesser_and_bigger(List, X) ->
  divide_to_lesser_and_bigger(List, X, [], []).

divide_to_lesser_and_bigger([H|L], X, Lesser, Bigger) when H < X ->
  divide_to_lesser_and_bigger(L, X, [H|Lesser], Bigger);
divide_to_lesser_and_bigger([H|L], X, Lesser, Bigger) when H >= X ->
  divide_to_lesser_and_bigger(L, X, Lesser, [H|Bigger]);
divide_to_lesser_and_bigger([], _, Lesser, Bigger) ->
  [reverse(Lesser)|reverse(Bigger)].

qsort([]) ->
  [];
qsort([H|L]) ->
  [Lesser|Bigger] = divide_to_lesser_and_bigger(L, H),
  concatenate([qsort(Lesser), H, qsort(Bigger)]).

instead of divide_to_lesser_and_bigger/2 use lists:partition(fun(A) -> A < H end, List).