Syntactic Confectionery Delight 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";

+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
Node Status?
node history
Node Type: snippet [id://113259]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (7)
As of 2018-02-21 08:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When it is dark outside I am happiest to see ...

Results (276 votes). Check out past polls.

Notices?