クイックソート(非再帰版) - うらでぃみーる通信 @Wiki

# クイックソート 非再帰版
 
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";
}