Jump to content

Sorting algorithms/Quicksort: Difference between revisions

imported>Joeypas
(Formatting again?)
imported>Rcmlz
Line 8,235:
# Partition.
my $before := @rest.grep(* before $pivot);
my $afterequiv := @rest.grep(* !beforeeqv $pivot);
my $after := @rest.grep(* after $pivot);
 
# Sort the partitions.
flat quicksort($before), $pivot, $equiv, quicksort($after)
}</syntaxhighlight>
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}}==
Anonymous user
Cookies help us deliver our services. By using our services, you agree to our use of cookies.