#!/usr/bin/perl

# implementation of the quicksort algorithm for demonstration and testing
# purposes.
#
# written and © by Jan 'jast' Krüger, 2003.
# See the enclosed file COPYING for licence details.

use warnings;
use strict;

# candy initialisation
my $swaps = 0;
my $compares = 0;
my $c2 = "\x1b[1;32m";
my $c1 = "\x1b[1;31m";
my $c0 = "\x1b[0;37m";

sub swap
{
	my ($ar, $a, $b) = @_[0..2];
	my $t;
	$t = $ar->[$b];
	$ar->[$b] = $ar->[$a];
	$ar->[$a] = $t;
	$swaps++;
}

sub cmpaa
{
	my ($ar, $a, $b) = @_[0..2];
	$compares++;
	$ar->[$a] cmp $ar->[$b];
}

sub cmpav
{
	my ($ar, $a, $b) = @_[0..2];
	$compares++;
	$ar->[$a] cmp $b;
}

sub cmpvv
{
	$compares++;
	$_[0] <=> $_[1];
}

sub part
{
	my ($l, $r, $array) = @_[0..2];
	my $p = $array->[$r];
	my ($i, $j) = ($l-1,$r);

	while(cmpvv($j, $i) > 0) {
		# the block IS necessary, really.
		do { $i++ } while(cmpav($array, $i, $p) < 0);
		do { $j-- } while(cmpav($array, $j, $p) > 0);
		swap($array, $i, $j);
	}
	swap($array, $i, $j);
	swap($array, $i, $r);

	return $i;
}

sub quicksort
{
	my ($l, $r, $array) = @_[0..2];

	return if(cmpvv($l, $r) >= 0);
	my ($oswaps, $ocompares) = ($swaps, $compares);
	my $p = part($l, $r, $array);

	# generate colourful visualisation of partitioning
	printf "(%3ss, %3sc)\t", ($swaps-$oswaps), ($compares-$ocompares);
	my @ap;
	push(@ap, join(' ', @$array[0..($l-1)])) if($l > 0);
	push(@ap, $c2 . join(' ', @$array[$l..($p-1)])) if($p > $l);
	push(@ap, $c1 . @$array[$p] . $c0);
	push(@ap, $c2 . join(' ', @$array[($p+1)..$r]) . $c0) if($r > $p);
	push(@ap, join(' ', @$array[($r+1)..(@$array-1)])) if((@$array-1) > $r);
	print join(' ', @ap) ."\n";

	quicksort($l, $p-1, $array);
	quicksort($p+1, $r, $array);
}

sub main {
	my @array = split(//, 'abcdefgEXAMPLE5732471238');

	print "start:\t\t". join(' ', @array) ."\n";
	quicksort(0, @array - 1, \@array);
	printf "%4ss, %3sc in total.\n", $swaps, $compares;
	print "explanation: s = swaps, c = compares, ".
	      "${c1}pivot element$c0, ${c2}partition$c0\n";
}

main();
