Simple bubble sort

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]

Comment on Simple bubble sort Download Code

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]
Re: Re (tilly) 1: Simple bubble sort by Anonymous Monk on Nov 12, 2014 at 19:19 UTC
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]
Re: Re: Simple bubble sort by blakem (Monsignor) on Sep 20, 2001 at 09:22 UTC
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]
Re: Re: Simple bubble sort by IndyZ (Friar) on Sep 19, 2001 at 23:50 UTC
Mostly I did it because I was bored, and I had never actually coded it before, even though I knew the theory. -- IndyZ	[reply]


Perl Monk, Perl Meditation
	PerlMonks