Beefy Boxes and Bandwidth Generously Provided by pair Networks
Come for the quick hacks, stay for the epiphanies.
 
PerlMonks  

Re: Algorithm Pop Quiz: Sorting

by RMGir (Prior)
on Mar 25, 2002 at 01:46 UTC ( [id://153988]=note: print w/replies, xml ) Need Help??


in reply to Algorithm Pop Quiz: Sorting

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)

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://153988]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others wandering the Monastery: (5)
As of 2024-03-29 10:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found