Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
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 making s'mores by the fire in the courtyard of the Monastery: (5)
As of 2014-12-28 09:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (179 votes), past polls