Sorting algorithms/Quicksort: Difference between revisions

Content added Content deleted
imported>Rcmlz
imported>Rcmlz
Line 8,247: Line 8,247:
multi quicksort-parallel(@unsorted where @unsorted.elems < 2) { @unsorted }
multi quicksort-parallel(@unsorted where @unsorted.elems < 2) { @unsorted }
multi quicksort-parallel(@unsorted) {
multi quicksort-parallel(@unsorted) {
⚫
# separate unsorted input into Order Less, Same and More compared to a random $pivot
my $pivot = @unsorted.pick;
my $pivot = @unsorted.pick;

⚫
# separate unsorted input into Order Less, Same and More compared to $pivot
my %partitions{Order} is default([]) = @unsorted.classify( * cmp $pivot );
my %partitions{Order} is default([]) = @unsorted.classify( * cmp $pivot );


# atomically decide if we sort the Less partition on a new worker thread
# atomically decide if we sort the Less partition on a new thread
my $less = ⚛$worker > 0 &&
my $less = ⚛$worker > 0 &&
%partitions{Less}.elems > $BATCH-SIZE
%partitions{Less}.elems > $BATCH-SIZE
?? start {
?? (
ENTER $worker⚛--;
$worker⚛--;
LEAVE $worker⚛++;
start {
samewith(%partitions{Less})
LEAVE $worker⚛++;
}
samewith(%partitions{Less})
}
)
!! samewith(%partitions{Less});
!! samewith(%partitions{Less});


Line 8,333: Line 8,334:
<pre>
<pre>
Benchmarking by sorting 40960 strings of size 8 - using batches of 1024 strings and 4 workers.
Benchmarking by sorting 40960 strings of size 8 - using batches of 1024 strings and 4 workers.
[quicksort => 5.271144286 quicksort-parallel => 2.645456851]
[quicksort => 4.691771502 quicksort-parallel => 1.296705289]
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Quicksort"