Skip to content

Instantly share code, notes, and snippets.

@ka8725 ka8725/qsort.erl
Last active Mar 2, 2016

Embed
What would you like to do?
% **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)]).
@fogfish

This comment has been minimized.

Copy link

commented Dec 27, 2015

use lists:reverse/1

@egobrain

This comment has been minimized.

Copy link

commented Mar 1, 2016

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.