Anonymous user
Sorting algorithms/Quicksort: Difference between revisions
→{{header|Raku}}
imported>Joeypas (Formatting again?) |
imported>Rcmlz |
||
Line 8,235:
# Partition.
my $before := @rest.grep(* before $pivot);
my $after := @rest.grep(* after $pivot);
Note that <code>$before</code> and <code>$after</code> are bound to lazy lists, so the partitions can (at least in theory) be sorted in parallel.
<syntaxhighlight lang="raku" line>
#|« Recursive, parallel quicksort implementation.
concurrency applied
* in partitioning step by .hyper or .race
* in recursion steps by start {}
»
sub quicksort-recursive-parallel(@input) {
return @input if @input.elems < 2;
my $pivot = @input.pick;
@input.race.classify(-> $element { $element cmp $pivot })
andthen
▲ {
my %partiton = $_;
my $less = start { %partiton{Less}:exists ?? samewith(%partiton{Less}) !! [] };
my $more = start { %partiton{More}:exists ?? samewith(%partiton{More}) !! [] };
await $less, $more;
|$less.result, |%partiton{Same}, |$more.result
}
}
#=« Implementation notes:
* samewith() refactors out the actual name of the routine.
* andthen passes output of previous block as $_ to the next block, alternatively use ==>
»
</syntaxhighlight>
Let's run some tests
<syntaxhighlight lang="raku" line>
use Test;
my @testcases =
() => (),
<a>.List => <a>.List,
<a a> => <a a>,
<b a> => <a b>,
<h b a c d f e g> => <a b c d e f g h>,
(2, 3, 1, 4, 5) => (1, 2, 3, 4, 5),
<a 🎮 3 z 4 🐧> => <a 🎮 3 z 4 🐧>.sort,
;
for &quicksort, &quicksort-recursive-parallel -> &fun {
is-deeply &fun(.key), .value, .key ~ "\t->\t" ~ .value for @testcases;
}
</syntaxhighlight>
=={{header|Red}}==
| |||