Beefy Boxes and Bandwidth Generously Provided by pair Networks Joe
There's more than one way to do things
 
PerlMonks  

Simple bubble sort

by IndyZ (Friar)
on Sep 19, 2001 at 08:23 UTC ( #113259=snippet: print w/ replies, xml ) Need Help??

Description: 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;
            }
        }
    }
}

Comment on Simple bubble sort
Download Code
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.

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

      --
      IndyZ
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

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;
    Things that follow the form:
    t=a; a=b; b=t;
    Can be reduced in Perl to:
    (a,b)=(b,a);
    So shorten that block of code to:
    ($array->[$i+1],$array->[$i])= ($array->[$i],$array->[$i+1]);
      Since we can assign into an array slice, it can be shortened down to something like:
      @$array[$i,$i+1] = @$array[$i+1,$i];
      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

      -Blake

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;
    While *ahem* inefficient, I think that this probably is more DWIM in different contexts.
Re: Simple bubble sort
by Anonymous Monk on Nov 14, 2008 at 07:30 UTC

    Back to Snippets Section

    Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Node Status?
    node history
    Node Type: snippet [id://113259]
    help
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others perusing the Monastery: (5)
    As of 2014-04-21 09:02 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      April first is:







      Results (492 votes), past polls