#!/usr/bin/perl -w
# 演算法: quick sort
# 作者: 洪朝貴 http://www.cyut.edu.tw/~ckhung
# 授權: public domain (但如果您要將我的程式改寫成有用的大程式,
#	強烈建議將您的版本施以 GPL)
# 執行方式: ./qsort -g -p left
#     其中 -g 為 debug 模式, 用以顯示過程
#          -p 指定 pivot 選取方式, 後面可以是 left, right,
#             mo3 (median of 3), rand (亂數)

use Getopt::Std;
use strict;

my (%opts);
my (%pick_pivot) = ( # function table for picking pivot
    "left" => sub { return $_[1]; },
    "right" => sub { return $_[2]; },
    "rand" => sub { my ($data, $i, $j) = @_; return $i + rand($j+1-$i); },
    "mo3" => \&mo3,
);

sub mo3 {
    my ($data, $i, $j) = @_;
    return $i if ($j-$i <= 1);
    my ($k) = int(($i+$j) / 2);
    return $data->[$i] < $data->[$j] ?
		$data->[$j] < $data->[$k] ? $j :
		    $data->[$i] < $data->[$k] ? $k : $i	:
		$data->[$j] > $data->[$k] ? $j :
		    $data->[$i] < $data->[$k] ? $i : $k;
}

sub dump_array {
    my ($data, $left, $right) = @_;
    print "   " x ($left+1);
    for (my $k=$left; $k<=$right; ++$k) {
	printf "%3d", $data->[$k];
    }
    print "\n";
}

sub partition {
    # always assuming the leftmost element to be the pivot
    my ($data, $left, $right) = @_;
    my ($pivot) = $data->[$left];
    my ($i, $j) = ($left, $right+1);
    dump_array($data, $left, $right) if ($opts{g});	# debug
    while (1) {
	while ($data->[++$i] < $pivot) {}
	while ($data->[--$j] > $pivot) {}
	if ($opts{g}) {     # debug
	    my ($mark) = "   " x ($right - $left + 2);
	    substr($mark, ($i-$left+1)*3, 3) = "  >";
	    substr($mark, ($j-$left+1)*3, 3) = "  <";
	    substr($mark, ($j-$left+1)*3, 3) = "  X"
		if $i == $j;
	    print "   " x $left, "$mark\n";
	}
	return $j if $i >= $j;
	@{$data}[$i,$j] = @{$data}[$j,$i];
    }
}

sub qsort {
    my ($data, $left, $right) = @_;
    return if $right <= $left;
    my ($pi) = & { $pick_pivot{$opts{p}} } ($data, $left, $right);
    if ($opts{g}) {
	dump_array($data, $left, $right);
	print "   " x ($pi+1), "  p\n" 
    }
    @{$data}[$pi, $left] = @{$data}[$left, $pi];
    my ($k) = partition($data, $left, $right);
    @{$data}[$k, $left] = @{$data}[$left, $k];
    qsort($data, $left, $k-1);
    qsort($data, $k+1, $right);
}

sub pusage {
    print STDERR "usage: $0 [-g] [-p pivot]\n",
	"where pivot may be one of: ", join(" ", sort keys %pick_pivot), "\n";
}

getopts('gp:', \%opts);
if (defined $opts{p}) {
    if (not defined $pick_pivot{$opts{p}}) {
	pusage();
	exit;
    }
} else {
    $opts{p} = "left";
}

my (@a);
@a = qw(15 62 16 25 65 18 20  3 14  8 93 84 62 18 81 51 47 80);
#@a = qw(8 6 1 3 5 2 4 7 9 3 5 4 8 3 1 0 6 7 3);
#@a = qw(6 7 3 8 6 1 3 5 2 4 6 7 9);

push @a, 999; # sentinel
print "     pivot: $opts{p}\n\n" if ($opts{g});	# debug
qsort(\@a, 0, $#a-1);
print "   ", "---" x ($#a + 1), "\n";
dump_array(\@a, 0, $#a-1);
print "\n\n";