Perlでクイックソート
wikipediaのCのサンプルをPerlに起こした感じのやつ。
無駄に再帰回数が多い気がしなくもない。
どっか間違ったかも。
#!/usr/bin/env perl use strict; use warnings; my @a = (3, 2, 0, 5, 8, 3, 4, 1, 3, 2); my @b = @a; qs(\@b, 0, $#b); print @a, "\n"; print @b, "\n"; sub qs { my ($a, $left, $right) = @_; my ($i, $j) = ($left, $right); my $pivot = $a->[$i]; while(1){ while($a->[$i] < $pivot){ $i++ } while($a->[$j] > $pivot){ $j-- } last if $i >= $j; ($a->[$i], $a->[$j]) = ($a->[$j], $a->[$i]); $i++; $j--; } return if $left >= $right; qs($a, $left, $i - 1); qs($a, $j + 1, $right); }
配列リファレンス渡しじゃなくて、結果の配列を連結してみた。
再帰は少ないけど上のより遅い。 あとメモリも食いそう。
#!/usr/bin/env perl use strict; use warnings; my @a = (3, 2, 0, 5, 8, 3, 4, 1, 3, 2); my @b = @a; @b = qs(@b); sub qs { my $t = $_[0]; my (@same, @high, @low); for(@_){ push @same, $_ if $_ == $t; push @high, $_ if $_ > $t; push @low, $_ if $_ < $t; } @high = qs(@high) if @high > 1; @low = qs(@low) if @low > 1; return map { $_ if defined } @low, @same, @high; }