A parallel quicksort implementation using Erlang
utils: mainly list manipulation functions, used by other modules ;quicksort: parallel sorting functions ;comparator: tools for benchmarking.
The list length N must be a power of two for the sorting algorithm to work. The list is first split into N/P parts of length P, and there will then be N/P processes working together through several steps in order to sort the global list. Each process will work on a different part of the global list.
The result is a list of lists. Since each sublist is the one that was
finally returned by a given process, the sublists' sizes homogeneity
allows to know if the sort was fairly distributed. You can then call
lists:flatten/1 in order to get a flattened version of the list.
dentuk@tank ~/git/parasortuk $ erl
Eshell V5.10.4 (abort with ^G)
1> c(utils).
{ok,utils}
2> c(quicksort).
{ok,quicksort}
3> N = 16, L0 = utils:generate_data(N).
[0.4435846174457203,0.7230402056221108,0.94581636451987,
0.5014907142064751,0.311326754804393,0.597447524783298,
0.915656206971831,0.6669572934854013,0.47712105608919275,
0.5965100813402789,0.14210821770124227,0.20944855618709624,
0.6971407843005519,0.15981142006315596,0.5582558083752902,
0.21497304823532137]
4> P = 4, L1 = quicksort:sort(L0, N, P).
[[0.14210821770124227,0.15981142006315596,
0.20944855618709624,0.21497304823532137,0.311326754804393,
0.4435846174457203],
[0.47712105608919275,0.5014907142064751],
[0.5582558083752902,0.5965100813402789],
[0.597447524783298,0.6669572934854013,0.6971407843005519,
0.7230402056221108,0.915656206971831,0.94581636451987]]
5> L2 = lists:flatten(L1).
[0.14210821770124227,0.15981142006315596,
0.20944855618709624,0.21497304823532137,0.311326754804393,
0.4435846174457203,0.47712105608919275,0.5014907142064751,
0.5582558083752902,0.5965100813402789,0.597447524783298,
0.6669572934854013,0.6971407843005519,0.7230402056221108,
0.915656206971831,0.94581636451987]In order to enable debug mode, define the debug macro
when compiling the quicksort module, for instance:
c(quicksort, {d, debug})..