in reply to bubble sort in perl

Keep in mind that bubble sort is one of the worst known sorting approaches. But given that, here's your sort (I gotta stop answering homework questions...)

This isn't even an EFFICIENT bubble sort (hehe), since "isSorted" could be done as part of the bubbling loop, by bubbling until no swaps occur. But this version is probably easier to read. 

sub bubble {
   my $arrRef=shift;

   foreach my $i(1..@$arrRef-1) {
      @$arrRef[$i,$i-1]=@$arrRef[$i-1,$i] 
            unless $arrRef->[$i-1]<=$arrRef->[$i];
   }
}

sub isSorted {
   my $arrRef=shift;
   my $isSorted=0;

   foreach my $i(1..@$arrRef-1) {
      return 0 unless $arrRef->[$i-1]<=$arrRef->[$i];
   }

   return 1;
}

open(IN,"<raw_data") or die "Can't open raw_data, error $!";
my @raw_data=map {chomp;$_} <IN>;

print "Before sort: ",(join ",",@raw_data), "\n";
bubble(\@raw_data) while !isSorted(\@raw_data);
print "After sort: ",(join ",",@raw_data), "\n";

[download]

If this IS for homework, try to understand it before handing it in, k? Otherwise, your teacher's gonna ask you some tough questions, and you're going to be in deep trouble...

Besides, if your teacher likes perl enough to teach it, he probably hangs out here with us anyhow :)
--
Mike

Replies are listed 'Best First'.
Re: Re: bubble sort in perl
by particle (Vicar) on Mar 24, 2002 at 13:39 UTC
    Keep in mind that bubble sort is one of the worst known sorting approaches.

    ...for generalized data. for almost sorted data, it's the best algorithm. if you're maintaining a list of sorted data, adding a few items, and re-sorting, this may be the way to go.

    ~Particle ;Þ

[reply]
      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

[reply]
        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]
Re: Re: bubble sort in perl
by Juerd (Abbot) on Mar 24, 2002 at 22:31 UTC

    Okay, here's a somewhat more efficient numeric bubble sort. (taking a list instead of arrayref, just like perl's sort.) 

    sub bubble {
    my @array = @_;
    for my $i (0..$#array) {
        for my $j (0..$i) {
            @array[$i, $j] = @array[$j, $i]
                if $array[$i] < $array[$j];
        }
    }
    return @array;
}

    [download]


    But:

    Thou shalt not sort with bubbles!

    Perl's sort is a lot easier, and a hell of a lot more efficient. If this is a homework assignment, and it probably is, don't just use our answers, but try to figure out WHY it works, and then tell your teacher real coders use sort instead.

    If it's part of a job application test, make sure you're not dealing with talexb and go ahead with a more efficient sort. 

    U28geW91IGNhbiBhbGwgcm90MTMgY
W5kIHBhY2soKS4gQnV0IGRvIHlvdS
ByZWNvZ25pc2UgQmFzZTY0IHdoZW4
geW91IHNlZSBpdD8gIC0tIEp1ZXJk

[reply]
[d/l]

In Section Seekers of Perl Wisdom