「クイックソート(非再帰版)」の編集履歴(バックアップ)一覧はこちら
「クイックソート(非再帰版)」(2009/10/11 (日) 23:00:45) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
//perl/linenumber
# クイックソート 非再帰版
use strict;
use warnings;
my $LIST_SIZE ||= 20;
my @list;
for(my $i = 0; $i < $LIST_SIZE; $i++){
$list[$i] = int($i);
}
#ランダムに並び替える
srand;
for (my $i = @list; --$i; ) {
my $j = int rand ($i + 1);
next if $i == $j;
@list[$i, $j] = @list[$j, $i];
}
# ソート前の状態表示
&ShowData();
# ソート実行
&QSort(0, $LIST_SIZE - 1);
# ソート後の状態表示
&ShowData();
sub QSort{
my $begin = shift;
my $end = shift;
my @left_stack;
my @right_stack;
my $sp = 1;;
my $left = 0;
my $right = 0;
$left_stack[0] = $begin;
$right_stack[0] = $end;
while( $sp > 0){
# スタックPOP
--$sp;
$left = $left_stack[$sp];
$right = $right_stack[$sp];
if($left < $right){
my $pivot = $list[int(($left + $right) / 2)];
my $i = $left;
my $j = $right;
while(1){
while($list[$i] < $pivot){$i++;}
while($list[$j] > $pivot){$j--;}
if($i >= $j){ last; }
($list[$i], $list[$j]) = ($list[$j], $list[$i]);
&ShowData(); # 途中表示
$i++;
$j--;
}
# スタックPUSH
if($i - $left < $right - $i){
$left_stack[$sp] = $j + 1;
$right_stack[$sp++] = $right;
$left_stack[$sp] = $left;
$right_stack[$sp++] = $i - 1;
}else{
$left_stack[$sp] = $left;
$right_stack[$sp++] = $i - 1;
$left_stack[$sp] = $j + 1;
$right_stack[$sp++] = $right;
}
}
}
}
# リスト表示
sub ShowData{
for my $a(@list){
print $a," ";
}
print "\n";
}
//perl/linenumber
# クイックソート 非再帰版
use strict;
use warnings;
my $LIST_SIZE ||= 20; # 要素数
my @list;
# 0から1増分のリストを作成
for(my $i = 0; $i < $LIST_SIZE; $i++){
$list[$i] = int($i);
}
#ランダムに並び替える
srand;
for (my $i = @list; --$i; ) {
my $j = int rand ($i + 1);
next if $i == $j;
@list[$i, $j] = @list[$j, $i];
}
# ソート前の状態表示
&ShowData();
# ソート実行
&QSort(0, $LIST_SIZE - 1);
# ソート後の状態表示
&ShowData();
sub QSort{
my $begin = shift;
my $end = shift;
my @left_stack;
my @right_stack;
my $sp = 1;;
my $left = 0;
my $right = 0;
$left_stack[0] = $begin;
$right_stack[0] = $end;
while( $sp > 0){
# スタックPOP
--$sp;
$left = $left_stack[$sp];
$right = $right_stack[$sp];
if($left < $right){
my $pivot = $list[int(($left + $right) / 2)];
my $i = $left;
my $j = $right;
while(1){
while($list[$i] < $pivot){$i++;}
while($list[$j] > $pivot){$j--;}
if($i >= $j){ last; }
($list[$i], $list[$j]) = ($list[$j], $list[$i]);
&ShowData(); # 途中表示
$i++;
$j--;
}
# スタックPUSH
if($i - $left < $right - $i){
$left_stack[$sp] = $j + 1;
$right_stack[$sp++] = $right;
$left_stack[$sp] = $left;
$right_stack[$sp++] = $i - 1;
}else{
$left_stack[$sp] = $left;
$right_stack[$sp++] = $i - 1;
$left_stack[$sp] = $j + 1;
$right_stack[$sp++] = $right;
}
}
}
}
# リスト表示
sub ShowData{
for my $a(@list){
print $a," ";
}
print "\n";
}
表示オプション
横に並べて表示:
変化行の前後のみ表示: