クイックソート
use strict;
use 5.012;
use Data::Dumper;
use POSIX qw/floor/;
my @nums = (30,80,70,10,50,20,40,90,60);
printf "ORIG: %s\n", join( ',', (map {sprintf '%4d', $_} @nums ));
quick_sort(0, $#nums);
printf "\nRESULT: %s\n", join( ',', (map {sprintf '%4d', $_} @nums ));
sub quick_sort {
my ( $i, $j ) = @_;
my ( $left, $right ) = ( $i, $j );
my $_pivot = floor( ( $i + $j ) / 2 );
my $pivot = $nums[$_pivot];
printf "\nNUMS: %s\n", join( ',', ( map { sprintf '%3d', $nums[$_] } $left .. $right ) );
printf "LEFT: [$left]\n";
printf "RIGHT: [$right]\n";
printf "PIVOT: $pivot\n";
while ( $i < $j ) {
while ( $nums[$i] < $pivot ) { $i++; }
while ( $nums[$j] > $pivot ) { $j--; }
if ( $i < $j ) {
printf "SWAP: %d,%d [%d,%d]\n", $nums[$i], $nums[$j], $i, $j,;
my $temp = $nums[$i];
$nums[$i] = $nums[$j];
$nums[$j] = $temp;
printf "NUMS: %s\n", join( ',', ( map { sprintf '%3d', $nums[$_] } $left .. $right ) );
}
}
printf "DIVIDE: %d,%d [%d,%d] \n", $nums[$i], $nums[$j], $i, $j;
if ( $left < $i - 1 ) {
quick_sort( $left, $i - 1 );
}
if ( $j + 1 < $right ) {
quick_sort( $j + 1, $right );
}
};
- 配列の中からPIVOT(枢軸数)を決める。以下の例では50。
- 50の左側に50より小さい数を、50の右側に50より大きい数を振り分ける。
- 振り分け終わったら、50の左側に2個以上の配列がないか調べる。あれば、その2個以上の配列をさらにクイックソートする。
- また、50の右側に2個以上の配列がないか調べて、あればその2個以上の配列をさらにクイックソートする。
ORIG: 30, 80, 70, 10, 50, 20, 40, 90, 60
NUMS: 30, 80, 70, 10, 50, 20, 40, 90, 60
LEFT: [0]
RIGHT: [8]
PIVOT: 50
SWAP: 80,40 [1,6]
NUMS: 30, 40, 70, 10, 50, 20, 80, 90, 60
SWAP: 70,20 [2,5]
NUMS: 30, 40, 20, 10, 50, 70, 80, 90, 60
DIVIDE: 50,50 [4,4]
NUMS: 30, 40, 20, 10
LEFT: [0]
RIGHT: [3]
PIVOT: 40
SWAP: 40,10 [1,3]
NUMS: 30, 10, 20, 40
DIVIDE: 40,40 [3,3]
NUMS: 30, 10, 20
LEFT: [0]
RIGHT: [2]
PIVOT: 10
SWAP: 30,10 [0,1]
NUMS: 10, 30, 20
DIVIDE: 10,10 [0,0]
NUMS: 30, 20
LEFT: [1]
RIGHT: [2]
PIVOT: 30
SWAP: 30,20 [1,2]
NUMS: 20, 30
DIVIDE: 30,30 [2,2]
NUMS: 70, 80, 90, 60
LEFT: [5]
RIGHT: [8]
PIVOT: 80
SWAP: 80,60 [6,8]
NUMS: 70, 60, 90, 80
SWAP: 90,80 [7,8]
NUMS: 70, 60, 80, 90
DIVIDE: 80,80 [7,7]
NUMS: 70, 60
LEFT: [5]
RIGHT: [6]
PIVOT: 70
SWAP: 70,60 [5,6]
NUMS: 60, 70
DIVIDE: 70,70 [6,6]
RESULT: 10, 20, 30, 40, 50, 60, 70, 80, 90
参考