Problems? Is your data what you think it is? PerlMonks

### Simple bubble sort

by IndyZ (Friar)
 on Sep 19, 2001 at 08:23 UTC 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;
}
}
}
}
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;
While *ahem* inefficient, I think that this probably is more DWIM in different contexts.
Glad this is at the end. Couldnt take much more.
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;
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: 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 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

Create A New User
Domain Nodelet?
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 having an uproarious good time at the Monastery: (3)
As of 2022-08-08 04:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?