Sorting algorithms/Quicksort: Difference between revisions

Content added Content deleted

Inline

@@ Line 8,235: / Line 8,235: @@
      # Partition.
      my $before := @rest.grep(* before $pivot);
-     my $after  := @rest.grep(* !before $pivot);
+	 my $equiv  := @rest.grep(* eqv $pivot);
+	 my $after  := @rest.grep(* after $pivot);
-     # Sort the partitions.
+	 # Sort the partitions.
-     flat quicksort($before), $pivot, quicksort($after)
+	 flat quicksort($before), $pivot, $equiv, quicksort($after)
- }</syntaxhighlight>
+}</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}}==