(Cross-posted to the Perl Beginners List)

On Nov 15, Tommy Butler said:

>What's a "bubble sort" ?  I believe I heard the term used on this list a
>while back.  I have some kind of idea of what it is, and how it would be
>implemented, but I'd like to find out for sure.  Could someone tell me
>what it is, under what circumstances is it beneficial, what are the
>benefits, how it is implemented, and how does it work?

Bubble sort is a naive sorting algorithm.  It's called "bubble" sort
because the larger elements "rise" to the "top" of the list, like a bubble
in water.  You compare two adjacent items in a list -- if the left is
larger than the right, you swap them; if not, do nothing.  Then, you move
the bubble up one element.  You continue this process until you don't need
to swap any more.

Here is a simple demonstration of the algorithm:

  LIST = 5  7  3  2  8  4
        [5  7] 3  2  8  4
         5 [7  3] 2  8  4
         5  3 [7  2] 8  4
         5  3  2 [7  8] 4
         5  3  2  7 [8  4]
         5  3  2  7  4  8

That was just ONE pass.  In a list of N elements, you will need at most N
passes (and that is when the list is in REVERSED order).  If the list is
already sorted, you only need ONE pass.

Here is a Perl implementation of bubble sort.  This sorting technique is
not very useful anymore, since things like heaps are around.  Still, it is
one of the first sorting techniques computer science students learn.

  sub bubble {
    my $a = shift;
    my $swap = 1;  # did we have to swap?

    while ($swap) {
      $swap = 0;  # assume we don't have to swap

      for $i (0 .. @$a - 2) {
        if ($a->[$i] > $a->[$i+1]) {    # if LEFT > RIGHT
          @$a[$i,$i+1] = @$a[$i+1,$i];  # swap them
          $swap = 1;                    # we had a swap
        }
      }
    }
  }

And that's it.

-- 
Jeff "japhy" Pinyan      [EMAIL PROTECTED]      http://www.pobox.com/~japhy/
RPI Acacia brother #734   http://www.perlmonks.org/   http://www.cpan.org/
** Look for "Regular Expressions in Perl" published by Manning, in 2002 **


-- 
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]

Reply via email to