Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
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.
      Glad this is at the end. Couldnt take much more.
Reaped: Re: Simple bubble sort
by NodeReaper (Curate) 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 cooling their heels in the Monastery: (12)
As of 2015-01-29 14:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My top resolution in 2015 is:

















    Results (238 votes), past polls