Ah, the bubble sort. Every computer science student loves it for it's simplicity, and hates it for it's unbelievable innefficiency. This example of a bubble sort takes an array ref and sorts the array in-place, from low to high. The array should be only numbers, no strings or other sneaky stuff.

Usage: bbl_sort(\@array);

For the curious, sorting a 10,000 element array of unique numbers on my 1.2 Ghz Athlon takes about 3 minutes on a randomized array. The worst-case-scenario, with all of the numbers backwards (i.e., 40, 39, ..., 0), takes a few minutes more. About an hour ago I set the computer to task on a 100,000 element array of unique numbers that had been randomly mixed up, and it is still going.


sub bbl_sort {
    my $array = shift;
    my $not_complete = 1;
    my $index;
    my $len = ((scalar @$array) - 2);
    while ($not_complete) {
        $not_complete = 0;
        foreach $index (0 .. $len) {
            if (@$array[$index] > @$array[$index + 1]) {
                my $temp = @$array[$index + 1];
                @$array[$index + 1] = @$array[$index];
                @$array[$index] = $temp;
                $not_complete = 1;
            }
        }
    }
}

[download]

Replies are listed 'Best First'.
Re (tilly) 1: Simple bubble sort
by tilly (Archbishop) on Sep 20, 2001 at 07:43 UTC
    You can make it simpler with loop control. And I threw in some behaviour tricks, see if you can figure it out. :-) 
    # Simple bubble sort, written with an empty loop and with
# some convenience tricks depending on how it is called
sub bbl_sort {
  if (defined wantarray) {
    @_ = wantarray ? @_ : @{shift(@_)};
  }

  SCAN: {
    foreach (0..(@_-2)) {
      if ($_[$_] gt $_[$_+1]) {
        @_[$_, $_+1] = @_[$_+1, $_];
        redo SCAN;
      }
    }
  }

  wantarray ? @_ : [@_];
}

# Try it, showing one of the games
my ($first, $second, $third) = qw(not in order?);
bbl_sort($first, $second, $third);
print map "$_\n", $first, $second, $third;

    [download]
    While *ahem* inefficient, I think that this probably is more DWIM in different contexts.
[reply]
[d/l]
      Glad this is at the end. Couldnt take much more.
[reply]
Re: Simple bubble sort
by clintp (Curate) on Sep 20, 2001 at 05:45 UTC
    I'll let the others lecture you about bubble sorts. Lemme take this opportunity to show you something cool in Perl. See this code of yours: 
         my $temp = @$array[$index + 1];
     @$array[$index + 1] = @$array[$index];
     @$array[$index] = $temp;

    [download]
    Things that follow the form: 
         t=a;
     a=b;
     b=t;

    [download]
    Can be reduced in Perl to: 
         (a,b)=(b,a);

    [download]
    So shorten that block of code to: 
     ($array->[$i+1],$array->[$i])=
         ($array->[$i],$array->[$i+1]);

    [download]
[reply]
[d/l]
[select]
      Since we can assign into an array slice, it can be shortened down to something like: 
      @$array[$i,$i+1] = @$array[$i+1,$i];

      [download]
      See it in action below.... 
      #!/usr/bin/perl -wT
use strict;

my $arrayref = ['A','B','C','D'];
print "Before: ", join(' ',@$arrayref), "\n";

@$arrayref[1,2] = @$arrayref[2,1];         # assign into an array slic
+e

print "After : ", join(' ',@$arrayref), "\n";

=output
Before: A B C D
After : A C B D

      [download]

      -Blake

[reply]
[d/l]
[select]
Re: Simple bubble sort
by Zaxo (Archbishop) on Sep 19, 2001 at 09:55 UTC

    My guess is that the 100,000 element sort should take about 5 hours. Bubble sort is quadratic, so 10 times the data should take 100 times the time.

    After Compline,
    Zaxo

[reply]
Re: Simple bubble sort
by lemming (Priest) on Sep 19, 2001 at 09:36 UTC

    Quick question:
    Why? Perl has a builtin based on qsort.

    You do note it's inefficient. The builtin finishes the sort of 1,000,000 elements on a P3-650 in 10 seconds.

[reply]
      Mostly I did it because I was bored, and I had never actually coded it before, even though I knew the theory.

      --
      IndyZ
[reply]

Back to Cool Uses for Perl