Quiver in fear, for here is my unholy answer :)
#!/usr/bin/perl -w
use strict;
my @stack=qw(d b f a e c 6); # <-- bottom .. top -->
# You are not allowed to modify this.
sub rotate_up {
local($a,$b);
$a=$_[0];
$a--;
return if $a<1;
$b=pop @stack;
splice(@stack, -$a, 0, $b);
}
sub sortIt {
print "before stack is ",(join ", ",@stack),"\n";
my $initLen=pop @stack;
my $currLen=$initLen;
# strategy: find the largest element, push it to bottom.
# reduce size by one, repeat
while($currLen) {
my $max;
my $rot=$currLen;
my $maxLoc=-1;
#print "Len $currLen, stack is ",(join ",", @stack),"\n";
# find largest element, and save its position
while($rot>=1) {
my $x=pop @stack;
if (!defined $max || ($x gt $max)) {
$maxLoc=$rot;
$max=$x;
}
push @stack, $x;
rotate_up($rot) if($rot>1);
$rot--;
#print "examined $x, max is ($maxLoc, $max), stack is ",(j
+oin ",", @stack),"\n";
}
# bring largest elem back up to top
while($maxLoc>1) {
rotate_up($maxLoc--);
#print "bumping up, stack is ",(join ",", @stack),"\n";
}
# push it to bottom
rotate_up($currLen--);
}
push @stack, $initLen;
print "Finished, ending stack is ",(join ", ",@stack),"\n";
}
# initial test case
sortIt();
# test reversed
@stack=qw(a b c d e f 6); # <-- bottom .. top -->
sortIt();
# test sorted
sortIt();
# test 1 element stack
@stack=qw(f 1); # <-- bottom .. top -->
sortIt();
@stack=qw(a a f a a 5); # <-- bottom .. top -->
sortIt();
# empty stack
@stack=qw(0); # <-- bottom .. top -->
sortIt();
# make sure items below stack aren't touched
@stack=qw(dontmoveme1 dontmoveme2 a a f a a 5); # <-- bottom .. top -
+->
sortIt();
Works for me!
--
Mike
(Edit: Updated with comments, added test cases, made the sort code into a subroutine to make testing simpler, added "before and after" printouts for testing)