Sorting algorithms/Quicksort: Difference between revisions
Content added Content deleted
imported>Joeypas (Formatting again?) |
imported>Rcmlz |
||
Line 8,235: | Line 8,235: | ||
# Partition. |
# Partition. |
||
my $before := @rest.grep(* before $pivot); |
my $before := @rest.grep(* before $pivot); |
||
my $equiv := @rest.grep(* eqv $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. |
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}}== |
=={{header|Red}}== |