#!/usr/bin/perl
 
use Data::Dumper;
use POSIX qw(ceil floor);
use strict;
 
my @src = (35, 40, 12, 30, 94, 18, 6, 67);
#my @src = (8, 6, 2, 3, 7, 4);
#@src = reverse(@src);
 
our $ident = 0;
 
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;
}
 
sub print_marks
{
  my ($a, $x, $pos) = @_;
  my $str = " ";
  my $i = 0;
  for(my $j = 0; $j < scalar(@$a); $j++)
  {
    if ($j == $$pos[$i])
    {
      $str .= $x." ";
      $str .= (" " x length($$a[$j]));
 
      $i++;
      if ($i > scalar(@$pos) - 1)
      {
        last;
      }
    }
    else
    {
      $str .= (" " x length($$a[$j]));
      $str .= "  ";
    }
  }
  return $str;
}
 
sub partition
{
  my ($a, $l, $r, $x) = @_;
  my $i = $l - 1;
  my $j = $r;
 
  do
  {
    do
    {
      $i++;
    }
    until($$a[$i] <= $x);
 
    do
    {
      $j--;
    }
    until($j <= $i || $$a[$j] >= $x);
 
    print "i=$i, j=$j", $/;
    if ($i < $j)
    {
      print (" " x $ident);
      print print_marks($a, "x", [$i, $j]), $/;
 
      my $tmp = $$a[$i];
      $$a[$i] = $$a[$j];
      $$a[$j] = $tmp;
    }
  }
  until($i >= $j);
 
  if ($i != $r)
  {
    my $tmp = $$a[$i];
    $$a[$i] = $$a[$r];
    $$a[$r] = $tmp;
    print (" " x $ident);
    print print_marks($a, ".", [$i, $r]), $/;
  }
 
  return $i;
}
 
sub quicksort
{
  my ($a, $l, $r) = @_;
  $ident += 2;
  if ($l < $r)
  {
    print (" " x $ident);
    print print_array(\@src), $/;
    print (" " x $ident);
    print print_marks($a, "|", [$l, $r]), $/;
 
    my $x = $$a[$r];
    my $p = partition($a, $l, $r, $x);
    quicksort($a, $l, $p - 1);
    quicksort($a, $p + 1, $r);
  }
  $ident -= 2;
}
 
 
quicksort(\@src, 0, scalar(@src) - 1);