Sorting algorithms/Quicksort: Difference between revisions

<syntaxhighlight lang="raku" line># Empty list sorts to the empty list

multi quicksort([]) { () }

# Otherwise, extract first item as pivot...

multi quicksort([$pivot, *@rest]) {

# Partition.

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. The partitions can be sorted in parallel.

#|« Recursive, concurrent quicksort implementation

* in partitioning/classifying step by .race or .hyper

* in recursion step on Less partition by start {}

»

sub quicksort-recursive-concurrent(@input) {

return @input if @input.elems < 2;

my $pivot = @input.pick;

@input.race.classify( * cmp $pivot )

andthen

{

my %partiton = $_;

my $less = start { %partiton{Less}:exists ?? samewith(%partiton{Less}) !! [] };

my $more = %partiton{More}:exists ?? samewith(%partiton{More}) !! [];

await $less andthen |$less.result, |%partiton{Same}, |$more

}

* no need to start a new thread for More partition - as we better use current thread.

* hyper/race using default batch=64 and degree=4 -> tune it!

* recursion on the Less partition can create a large number of new threads -> limit it!

* samewith() refactors out the actual name of the routine.

* andthen passes the result of the previous block as $_ to the next block.

for &quicksort, &quicksort-recursive-parallel -> &fun {

is-deeply &fun(.key), .value, .key ~ "\t->\t" ~ .value for @testcases;