クイックソート

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

参考


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS

Last-modified: 2012-01-14 (土) 14:14:40 (2801d)