use strict; use warnings; { my @a = qw/3 2 0 5 8 3 4 1 3 2/; print join(',',@a) . "\n"; print "===================\n"; print join(',',sort(@a)) . "\n"; } sub pivot { my ($ar, $i, $j) = @_; my @a = @$ar; my $k = $i + 1; while ($k <= $j && $a[$i] == $a[$k]) { $k++; } return -1 if($k > $j); return $i if($a[$i] >= $a[$k]); return $k; } sub partition { my ($ar, $i, $j, $x) = @_; my @a = @$ar; my $l = $i; my $r = $j; while ($l <= $r) { while ($l <= $j && $a[$l] < $x) { $l++; } while ($r >= $i && $a[$r] >= $x) { $r--; } last if($l > $r); my $t = $a[$l]; $a[$l] = $a[$r]; $a[$r] = $t; $l++; $r--; } return ($l,\@a); } sub quick_sort { my ($a, $i, $j) = @_; return if($i == $j); my $p = pivot($a, $i, $j); if ($p != -1) { my $k; ($k,$a) = partition($a, $i, $j, $a->[$p]); $a = quick_sort($a, $i, $k-1); $a = quick_sort($a, $k, $j); } return $a; } sub sort { my @a = @_; my $length = @a; my $new_a = quick_sort(\@a,0,$length); return @$new_a; }
クイックソートは最も高速なソートアルゴリズムと言われています。(O(NlogN))
ただし、安定していないアルゴリズムなので、データによっては高速ではない場合があります(最悪O(N^2))
アルゴリズムとしては、まず基準となる値を配列の中から選びます(pivot())。
基準となった値をピボットと呼びます。
ピボットを基準にして配列を2つに分割します(partition())。
分割した配列それぞれに再帰的に同じ処理をしていきます(quick_sort())。
最終的にソートされた配列が出来上がります。