sub sort_stack {

  local $depth = pop @stack;
  local $sort_depth = $depth;

  for (1..$depth) {
    for (1..$sort_depth) {

      local $top  = pop @stack;
      local $next = pop @stack;

      if ($top gt $next) {

        $top  ^= $next;
        $next ^= $top;
        $top  ^= $next;

      }
      push @stack, $next, $top;
      rotate_up($sort_depth);
    }

    rotate_up($sort_depth);
    --$sort_depth;
  }
  push @stack, $depth;
}
[download]

Sure, it looks cool. It's just wrong :)

The problem with xor on strings is it will extend short ones. There are now 0 bytes there that weren't there before, and length changes.

$ perl -e'$a="a"; $b="bbb"; $a^=$b; $b^=$a; $a^=$b; print "/$a/,/$b/\n
+"; print length($a),"\n"; print length($b),"\n"'
/bbb/,/a/
3
3
[download]


--
Mike

Mike, thanks, I think. How odd. I had no idea this happened. That'll teach me. Still, I've never had a computer science lesson in my life, so how am I expected to know these things!?! :) Cheers, Jasper

BZZZT

I'm going to disallow this one as it's relying on a feature that's language dependent for its implementation (the XOR swap for stings). The sprit is there, but you're starting to wander. This kind of behavior needs to be discouraged early! Use the extra register for the swap. :)

These are all so good though. The excitement is terrible. Just terrible!

OK, here's the early-exit version. This proved more straight-forward than I was expecting. I was so sure that applying the knowledge of last-exchange would be difficult, I overlooked how trivial it actually is.

(This is still a bubble-sort, but it no longer is compelled to iterate [ $length - 1 ] times. Rather, the false-bottom can jump over several iterations if there is a clump of sorted elements at the end. Given the six-element sample list here, it saves only 3 iterations of the inner-loop, 17 versus 20 in my original.)

# Assume that rotate_up as defined in the original problem
# statement has been defined.

sub sordid
{
    local $len = pop(@stack);
    local $bum = $len;

    local ($x, $y, $limit, $last_swap);

    while ($bum > 1)
    {
        $limit = $bum;
        $last_swap = 0;
        while (--$limit)
        {
            $x = pop(@stack);
            $y = pop(@stack);

            if ($x gt $y)
            {
                push(@stack, $x);
                push(@stack, $y);
                $last_swap = $bum - $limit;
            }
            else
            {
                push(@stack, $y);
                push(@stack, $x);
            }

            rotate_up($bum);
        }
        # At end of the $limit loop, top element is the max, and
        # top+1 to end is semi-sorted. One more rotate_up()
        # is needed before moving the floor up one notch.
        rotate_up($bum);
        $bum = $last_swap;
    }

    push(@stack, $len);
}

@stack = qw(d b f a e c 6);  # <-- bottom .. top -->

print "(@stack)\n";
# Prints: (d b f a e c 6)
sordid();
print "(@stack)\n";
# Prints: (f e d c b a 6)
[download]

--rjray

Cool!
--
Mike