Compare sorting algorithms' performance: Difference between revisions
Compare sorting algorithms' performance (view source)
Revision as of 16:19, 14 November 2022
, 1 year agoadded Raku programming solution
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(added Raku programming solution) |
||
Line 2,927:
qsort - O(N*log(N))
qsortranpart - O(N) ???
=={{header|Raku}}==
{{trans|Julia}}
<syntaxhighlight lang="raku" line># 20221114 Raku programming solution
my ($rounds,$size) = 3, 2000;
my @allones = 1 xx $size;
my @sequential = 1 .. $size;
my @randomized = @sequential.roll xx $size;
sub insertion_sort ( @a is copy ) { # rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#Raku
for 1 .. @a.end -> \k {
loop (my ($j,\value)=k-1,@a[k];$j>-1&&@a[$j]>value;$j--) {@a[$j+1]=@a[$j]}
@a[$j+1] = value;
}
return @a;
}
sub merge_sort ( @a ) { # rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Raku
return @a if @a <= 1;
my $m = @a.elems div 2;
my @l = merge_sort @a[ 0 ..^ $m ];
my @r = merge_sort @a[ $m ..^ @a ];
return flat @l, @r if @l[*-1] !after @r[0];
return flat gather {
take @l[0] before @r[0] ?? @l.shift !! @r.shift
while @l and @r;
take @l, @r;
}
}
sub quick-sort(@data) { # andrewshitov.com/2019/06/23/101-quick-sort-in-perl-6/
return @data if @data.elems <= 1;
my ($pivot,@left, @right) = @data[0];
for @data[1..*] -> $x { $x < $pivot ?? push @left, $x !! push @right, $x }
return flat(quick-sort(@left), $pivot, quick-sort(@right));
}
sub comparesorts($rounds, @tosort) {
my ( $iavg, $mavg, $qavg, $t );
for (<i m q> xx $rounds).flat.pick(*) -> \sort_type {
given sort_type {
when 'i' { $t = now ; insertion_sort @tosort ; $iavg += now - $t }
when 'm' { $t = now ; merge_sort @tosort ; $mavg += now - $t }
when 'q' { $t = now ; quick-sort @tosort ; $qavg += now - $t }
}
}
return $iavg, $mavg, $qavg »/» $rounds
}
for <ones presorted randomized>Z(@allones,@sequential,@randomized) -> ($t,@d) {
say "Average sort times for $size $t:";
{ say "\tinsertion sort\t$_[0]\n\tmerge sort\t$_[1]\n\tquick sort\t$_[2]" }(comparesorts $rounds,@d)
}</syntaxhighlight>
{{out}}
<pre>Average sort times for 2000 ones:
insertion sort 0.112333083
merge sort 0.506624066
quick sort 5.899009606666667
Average sort times for 2000 presorted:
insertion sort 0.03596163
merge sort 0.474839352
quick sort 5.896118350666666
Average sort times for 2000 randomized:
insertion sort 5.352926729
merge sort 0.784896982
quick sort 0.11422247299999999</pre>
=={{header|REXX}}==
| |||