Skip to content

Instantly share code, notes, and snippets.

@tsujigiri
Created May 17, 2012 07:51
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save tsujigiri/2717257 to your computer and use it in GitHub Desktop.
Save tsujigiri/2717257 to your computer and use it in GitHub Desktop.
Parallel quicksort in Erlang
-module(quicksort).
-export([quicksort/2]).
quicksort(List, SpawnFactor) when SpawnFactor > 0 ->
Self = self(),
Child = spawn(fun() -> quicksort(Self, List, SpawnFactor) end),
receive
{Child, SortedList} -> SortedList
end.
quicksort(_, [], 0) ->
[];
quicksort(Parent, [], _) ->
Parent ! {self(), []};
quicksort(Parent, [Pivot|Tail], 0) ->
{Greater, LessOrEqual} = partition(Pivot, Tail),
quicksort(Parent, LessOrEqual, 0) ++ [Pivot | quicksort(Parent, Greater, 0)];
quicksort(Parent, [Pivot|Tail], 1) ->
{Greater, LessOrEqual} = partition(Pivot, Tail),
Parent ! {self(),
quicksort(Parent, LessOrEqual, 0) ++
[Pivot | quicksort(Parent, Greater, 0)]};
quicksort(Parent, [Pivot|Tail], SpawnFactor) ->
{Greater, LessOrEqual} = partition(Pivot, Tail),
Self = self(),
LPid = spawn(fun() -> quicksort(Self, LessOrEqual, SpawnFactor-1) end),
GPid = spawn(fun() -> quicksort(Self, Greater, SpawnFactor-1) end),
receive
{LPid, LResult} ->
receive
{GPid, GResult} ->
Parent ! {Self, LResult ++ [Pivot | GResult]}
end
end.
partition(Pivot, List) ->
partition(Pivot, List, [], []).
partition(_, [], Greater, LessOrEqual) -> {Greater, LessOrEqual};
partition(Pivot, [H|T], Greater, LessOrEqual) when H > Pivot ->
partition(Pivot, T, [H|Greater], LessOrEqual);
partition(Pivot, [H|T], Greater, LessOrEqual) ->
partition(Pivot, T, Greater, [H|LessOrEqual]).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment