Concurrent Quicksort
From CodeCodex
The Quicksort algorithm is based on choosing some element from the list to be sorted, and partitioning the remaining elements into those less than and greater than the chosen element, then recursively applying the algorithm to these partitions until we get down to single elements.
This can be implemented in a concurrent form, by representing the partitions as subtasks of the sorting task.
[edit] Ada
with ada.text_io;
use ada;
procedure parallel_quicksort is
type sort_item is -- sample data to be sorted
record
key : integer;
value : string(1 .. 7);
end record;
type sort_item_array is
array (integer range <>) of sort_item;
task type quicksort_filter is
-- implements the recursive quicksort, creating child instances of
-- itself as necessary.
entry input_item
(
item : sort_item
);
-- accepts another item from parent to be sorted.
entry end_input_items;
-- indicates no more input_item calls, but output_item calls will follow.
entry output_item
(
item : out sort_item;
got_item : out boolean
);
-- called to return another item in sorted order to parent, or will
-- set got_item to false to indicate all items done.
end quicksort_filter;
subtype qs_filter is quicksort_filter;
-- need another name for recursive use
task body quicksort_filter is
mid_item : sort_item;
got_mid_item : boolean;
less_than, greater_than : access qs_filter;
begin
got_mid_item := false;
loop -- collect unsorted items
select
accept input_item(item : sort_item) do
if not got_mid_item then
mid_item := item;
got_mid_item := true;
else
if item.key < mid_item.key then
if less_than = null then
less_than := new qs_filter;
end if;
less_than.input_item(item);
else -- if item.key >= mid_item.key then
if greater_than = null then
greater_than := new qs_filter;
end if;
greater_than.input_item(item);
end if;
end if;
end input_item;
or
accept end_input_items;
if less_than /= null then
less_than.end_input_items;
end if;
if greater_than /= null then
greater_than.end_input_items;
end if;
exit;
end select;
end loop;
-- now output collected items in sorted order
declare
next_item : sort_item;
got_next_item : boolean;
begin
if less_than /= null then
loop
less_than.output_item(next_item, got_next_item);
if not got_next_item then
exit;
end if;
accept output_item(item : out sort_item; got_item : out boolean) do
item := next_item;
got_item := true;
end output_item;
end loop;
end if;
if got_mid_item then
accept output_item(item : out sort_item; got_item : out boolean) do
item := mid_item;
got_item := true;
end output_item;
end if;
if greater_than /= null then
loop
greater_than.output_item(next_item, got_next_item);
if not got_next_item then
exit;
end if;
accept output_item(item : out sort_item; got_item : out boolean) do
item := next_item;
got_item := true;
end output_item;
end loop;
end if;
end;
accept output_item(item : out sort_item; got_item : out boolean) do
got_item := false;
end output_item;
end quicksort_filter;
the_items : sort_item_array :=
( -- key is wavelength, colours initially sorted by name
(475, "blue "),
(492, "cyan "),
(580, "gamboge"),
(510, "green "),
(445, "indigo "),
(540, "leafy "),
(590, "orange "),
(650, "red "),
(620, "scarlet"),
(400, "violet "),
(570, "yellow ")
);
sortem : quicksort_filter;
begin -- parallel_quicksort
-- feed in unsorted items
for i in the_items'range loop
sortem.input_item(the_items(i));
end loop;
sortem.end_input_items;
-- now collect and output sorted items
declare
next_item : sort_item;
got_next_item : boolean;
begin
loop
sortem.output_item(next_item, got_next_item);
if not got_next_item then
exit;
end if;
text_io.put_line(integer'image(next_item.key) & " => " & next_item.value);
end loop;
end;
end parallel_quicksort;
The output from running this program is
400 => violet 445 => indigo 475 => blue 492 => cyan 510 => green 540 => leafy 570 => yellow 580 => gamboge 590 => orange 620 => scarlet 650 => red
