in reply to Re: Re: bubble sort in perl
in thread bubble sort in perl

Well, not really.

It's better than some, but you'd really want to do a selection or insertion sort to add your new elements, I think, depending on your data structure.

The problem is that bubble sort only ever moves an element 1 spot. So if you add an element that would normally go into position 1 of a 1000-item list at the end of the pre-sorted list, you're looking at 1000 iterations over the whole list to "bump" it up into position 1. Ouch...
--
Mike

Replies are listed 'Best First'.
Re:(4) bubble sort in perl
by particle (Vicar) on Mar 24, 2002 at 14:29 UTC
    i suppose it depends on how you define almost sorted data. you're right about the example i provided (silly me.) but, if the list contains a few swapped elements, bubble is fast, fast, fast.

    enough about that. your code is broken. it only performs one pass through the data, so it will only sort one element. try something like: Update: i need to eat breakfast before i post any more... and i prefer the sort all in one sub, so here's mine (lifted from mastering algorithms, if i recall correctly:)

    sub bubble
{
    my @array = @{ $_[0] };
    for( my $i = $#array; $i; $i-- )
    {
        for( my $j = 1; $j <= $i; $j++ )
        {
            @array[$j, $j-1] = @array[$j-1, $j] 
                if( $array[$j-1] > $array[$j] );
        }
    }
    return \@array;
}
my $aRef = [ 2, 4, 3, 5, 1 ];
my $aSortedRef = bubble( $aRef );

print "@{$aRef}$/";
print "@{$aSortedRef}$/";

    [download]
    which iterates through the array backwards (the sorted data gathers on the tail end) and swaps elements until they're ordered.

    also, your code sorts data in-place. i modified it to sort to a new array, as it's my preference.

    ~Particle ;Þ

[reply]
[d/l]
      Broken is... wrong :)

      Check out the main loop: 

      bubble(\@raw_data) while !isSorted(\@raw_data);

      [download]
      Yours IS better, though.
      --
      Mike
[reply]
[d/l]

In Section Seekers of Perl Wisdom