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.

Ada[edit]

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