クイックソート

 sub quick_sort {
     printf "DEBUG: %s\n", join( ',', @nums );
     my ( $i, $j ) = @_;
     my ( $left, $right ) = ( $i, $j );
 
     my $pivot = int( ( $i + $j ) / 2 );
     say "DEBUG: PV:$pivot LEFT:$i RIGHT:$j";
 
     while ( $i < $j ) {
         while ( $nums[$i] < $nums[$pivot] ) { $i++; }
         while ( $nums[$j] > $nums[$pivot] ) { $j--; }
         if ( $i < $j ) {
             printf "DEBUG: SWAP: %d,%d\n", $nums[$i], $nums[$j];
             my $temp = $nums[$i];
             $nums[$i] = $nums[$j];
             $nums[$j] = $temp;
         }
     }
     if ( $left < $pivot - 1 ) {
         quick_sort( $left, $pivot - 1 );
     }
     if ( $pivot + 1 < $right ) {
         quick_sort( $pivot, $right );
     }
 }
 
 quick_sort(0, $#nums);
 say Dumper \@nums;

参考


トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS