#!/usr/bin/perl
 
use Data::Dumper;
use POSIX qw(ceil floor);
use strict;
 
our ($cnt, $cnt2) = 0;
 
my @src = ();
for(my $i = 0; $i < 100; $i++)
{
  push(@src, int(rand(500)));
}
 
my @src = (3, 1, 14, 4, 10, 5, 13);
#@src = reverse(@src);
 
our $ident = "";
 
sub print_array
{
  my ($a) = @_;
  my $str = "[";
  for(my $i = 0; $i < scalar(@$a); $i++)
  {
    $str .= ((defined($$a[$i])) ? $$a[$i] : "_");
    $str .= ", ";
  }
  $str = substr($str, 0, length($str)-2);
  $str .= "]";
  return $str;
}
 
print $ident, print_array(\@src), $/;
 
sub swap
{
  my ($a, $i, $j) = @_;
  my $tmp = $$a[$i];
  $$a[$i] = $$a[$j];
  $$a[$j] = $tmp;
  print $ident, print_array($a), $/;
}
 
sub run2
{
  my ($a, $left, $right) = @_;
  my $lastswap = 0;
  while ($left < $right)
  {
    $cnt++;
    my ($i, $j);
    for($j = $right; $j > $left; $j--)
    {
      $cnt2++;
      if ($$a[$j] < $$a[$j - 1])
      {
        swap($a, $j, $j-1);
        $lastswap = $j;
      }
    }
    print "lastswap=$lastswap", $/;
    $left = $lastswap;
 
    if ($lastswap == 0)
    {
      last;
    }
 
    for($i = $left; $i < $right; $i++)
    {
      $cnt2++;
      if ($$a[$i] > $$a[$i + 1])
      {
        swap($a, $i, $i+1);
        $lastswap = $i;
      }
    }
    print "lastswap=$lastswap", $/;
    $right = $lastswap;
    #run($a, $left+1, $right-1);
  }
}
 
sub run
{
  my ($a, $left, $right) = @_;
  while($left <= $right)
  {
    my ($i, $j);
    for($i = $left; $i < $right; $i++)
    {
      $cnt2++;
      if ($$a[$i] > $$a[$i + 1])
      {
        swap($a, $i, $i+1);
      }
    }
    for($j = $right; $j > $left; $j--)
    {
      $cnt2++;
      if ($$a[$j] < $$a[$j - 1])
      {
        swap($a, $j, $j-1);
      }
    }
    $right--;
    $left++;
  }
}
 
#$cnt = 0;
#my @a = @src;
#run(\@a, 0, scalar(@a) - 1);
#print $ident, "final=", print_array(\@a), $/;
#print "cnt=", $cnt, " cnt2=", $cnt2, $/;
 
$cnt = $cnt2 = 0;
my @a = @src;
print scalar(@a), $/;
run2(\@a, 0, scalar(@a) - 1);
print $ident, "final=", print_array(\@a), $/;
print "cnt=", $cnt, " cnt2=", $cnt2, $/;
 
 
exit;
 
my $swapped;
my $len = scalar(@a);
do
{
  $swapped = 0;
  for (my $i = 0; $i < $len - 1; $i++)
  {
    if ($a[$i] > $a[$i + 1])
    {
      my $tmp = $a[$i];
      $a[$i] = $a[$i+1];
      $a[$i+1] = $tmp;
      $swapped = 1;
      print $ident, print_array(\@a), $/;
    }
  }
  $len--;
}
while($swapped && $len > 0);
print $ident, print_array(\@a), $/;
 
exit;
for (my $i = 0; $i < scalar(@a); $i++)
{
  for(my $j = 1; $j < scalar(@a) - $i; $j++)
  {
    if ($a[$j] < $a[$j-1])
    {
      my $tmp = $a[$j];
      $a[$j] = $a[$j-1];
      $a[$j-1] = $tmp;
      print $ident, print_array(\@a), $/;
    }
  }
}
 
print $ident, print_array(\@a), $/;