クイックソート

 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