Jeff 'Japhy' Pinyan wrote:
>
> (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.
That looks like a direct translation of algorithm 5.2.2B from TAoCP Vol.
3 however the usual implementation is more like Sedgewick's example:
sub bubble {
my $a = shift;
for ( my $i = @$a; $i >= 1; $i-- ) {
for ( my $j = 2; $j <= $i; $j++ ) {
if ( $a->[ $j - 1 ] > $a->[ $j ] ) {
$a->[ $j - 1, $j ] = $a->[ $j, $j - 1 ];
}
}
}
}
John
--
use Perl;
program
fulfillment
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
