Newbie... bubble sort in a more elegant fashion?

[Will]

Hello!
I have some experience with a pascal in an intro to programming class, and I'm
trying to learn Perl. I wrote a bubble sort in Perl, but it is inelegant. I
believe I could use the tr/// operator to make this a better piece of code,
but I was at a loss as to how to do it! Please help! Thanks!

#!/usr/bin/perl
#sorted2.plx
use warnings;
use strict;

my $input="my.txt";
my $flag=0;
$_="";

#my $input=shift;
#my $output=shift;

open INPUT, "my.txt" or die "Couldn't open file $input: $\n";
open OUTPUT, ">issorted.txt" or die $!;

my @file=<INPUT>;
my $num=scalar @file;
my $count=0;
my $flag="";
my $temp1="";
my $temp2="";

while ($count<$num-1){

if (($file[$count]) gt ($file[$count+1])){
$temp1=$file[$count];
$temp2=$file[$count+1];

#switchem'
$file[$count]=$temp2;
$file[$count+1]=$temp1;

$flag=1;
}
$count++;
if ($flag && $count>=$num){$count=0; $flag="";}
}#exited while



#@file= sort @file;
print @file;

print OUTPUT @file;

 

[Walter Roberson]

:I have some experience with a pascal in an intro to programming class, and I'm
:trying to learn Perl. I wrote a bubble sort in Perl, but it is inelegant. I
:believe I could use the tr/// operator to make this a better piece of code,
:but I was at a loss as to how to do it! Please help! Thanks!

I can't imagine how the translate operator would help!


: if (($file[$count]) gt ($file[$count+1])){
: $temp1=$file[$count];
: $temp2=$file[$count+1];
: $file[$count]=$temp2;
: $file[$count+1]=$temp1;
: $flag=1;
: }

That can be reduced to a single statement in several different ways,
including:


@file[$count..$count+1] = @file[$count+1,$count] and $flag = 1
if $file[$count] gt $file[$count+1];

do { @file[$count..$count+1] = @file[$count+1,$count]; $flag = 1 }
if $file[$count] gt $file[$count+1];

 

[gnari]

Hello!
I have some experience with a pascal in an intro to programming class, and I'm
trying to learn Perl. I wrote a bubble sort in Perl, but it is inelegant. I
believe I could use the tr/// operator to make this a better piece of code,
but I was at a loss as to how to do it! Please help! Thanks!

if you just need a sort function, use the builtin function 'sort'

if this is just a perl exercise then here are some critisisms

#!/usr/bin/perl
#sorted2.plx
use warnings;
use strict;

my $input="my.txt";

some people will tell you that it is more elegant
to just use:
my $input='my.txt';
double quotes interpolate the test. as you are not using
variables or escapes, single quotes are cleaner

my $flag=0;
$_="";

no need to initialize these, specially as you do not
use them before the next assignement.

open INPUT, "my.txt" or die "Couldn't open file $input: $\n";

I assume you meant $! at the end of the error message
careful here: your open and error message do not match
what happens if you change $input
open INPUT, $input or die "Couldn't open file $input: $!";
even better is
open INPUT, "< $input" or die "Couldn't open file $input: $!";
this prevents bad things to happen if $input is accidentally (or not)
set to ">myimportantfile.txt"

open OUTPUT, ">issorted.txt" or die $!;

it is nicer to specify more in the error message
open OUTPUT, ">issorted.txt" or die "Could not open output file
'issorted.txt' $!";

my @file=<INPUT>;
my $num=scalar @file;

'scalar' here is not really needed
if you like this kind of things you can

my $count=0;
my $flag="";
my $temp1="";
my $temp2="";

$flag is redeclared
$count does not need to to be set to 0
the $temps do not need to be initialized
actually you do not need them at all (see below)

while ount<$num-1){

if (($file[$count]) gt ($file[$count+1])){

what happened to your indenting?

$temp1=$file[$count];
$temp2=$file[$count+1];
$file[$count]=$temp2;
$file[$count+1]=$temp1;

these 4 lines can be replaces by :
@file[$count,$count+1]=@file[$count+1,$count];

gnari

 

[Tore Aursand]

I have some experience with a pascal in an intro to programming class,
and I'm trying to learn Perl.

I wouldn't have started off with sort algorithms, but that's another side
of the story.

Algorithms doesn't change from language to language, neither do the bubble
sort algorithm.

$_="";

Don't do that.

open INPUT, "my.txt" or die "Couldn't open file $input: $\n";
open OUTPUT, ">issorted.txt" or die $!;

my @file=<INPUT>;
my $num=scalar @file;
my $count=0;
my $flag="";
my $temp1="";
my $temp2="";

while ($count<$num-1){

if (($file[$count]) gt ($file[$count+1])){ $temp1=$file[$count];
$temp2=$file[$count+1];

#switchem'
$file[$count]=$temp2;
$file[$count+1]=$temp1;

$flag=1;
}
$count++;
if ($flag && $count>=$num){$count=0; $flag="";}
}#exited while



#@file= sort @file;
print @file;

print OUTPUT @file;

I don't even bother trying to read this code, as it generally sucks. I
tried to write a bubble sort function a few months after I started
learning Perl, and I ended up with something like this (untested):

sub bubble_sort {
my $array = shift || [];

for ( my $x = $#$array; $x; $x-- ) {
for ( my $y = 1; $y <= $x; $y++ ) {
if ( $array->[$y-1] gt $array->[$y] ) {
@$array[$y, $y-1] = @$array[$y-1, $y];
}
}
}
}

In your case, at it seems like you're trying to sort the contents of a
file, you could use this function like this;

open(FILE, 'file.txt') or die "$!\n";
my @lines = <FILE>; # Beware of this when dealing with large files!
close(FILE);

bubble_sort( \@lines );
print join("\n", @lines);

As far as I remember, it worked quite well. It's also a "direct copy" of
a bubble sort function I learned back in 1992 while learning Turbo Pascal,
but it was _a lot_ easier to write it with Perl of course.

I haven't studied the bubble sort algorithm above much, but I'd appreciate
anyone taking the effort to optimize it (as I'm sure it's possible).

 

[Tad McClellan]

:I have some experience with a pascal in an intro to programming class, and I'm
:trying to learn Perl. I wrote a bubble sort in Perl, but it is inelegant. I
:believe I could use the tr/// operator to make this a better piece of code,
:but I was at a loss as to how to do it! Please help! Thanks!

I can't imagine how the translate operator would help!

^^^^^^^^^

It is the "transliteration operator".

: if (($file[$count]) gt ($file[$count+1])){
: $temp1=$file[$count];
: $temp2=$file[$count+1];
: $file[$count]=$temp2;
: $file[$count+1]=$temp1;
: $flag=1;
: }

That can be reduced to a single statement in several different ways,

[snip ways]


Right, but the result doesn't seem appropriate for someone new
to both Perl and programming itself.

If the OP wants to take smaller steps, then I'll offer yet another way.

Eliminate do-nothing punctuation and do the swapping with a
"list assignment" to avoid the silly temp variables:

if ( $file[$count] gt $file[$count+1] ) { # untested
($file[$count], $file[$count+1]) = ($file[$count+1], $file[$count]);
$flag=1;
}

 

[Tad McClellan]

use warnings;

Enabling warnings is good.

Very good.

my $flag=0;

[snip code]

my $flag="";

Ignoring the warnings that are generated is bad.

Very bad.



Try to make your code free of all warnings.

 

[Anno Siegel]

[bubble sort]

tried to write a bubble sort function a few months after I started
learning Perl, and I ended up with something like this (untested):

sub bubble_sort {
my $array = shift || [];

for ( my $x = $#$array; $x; $x-- ) {
for ( my $y = 1; $y <= $x; $y++ ) {
if ( $array->[$y-1] gt $array->[$y] ) {
@$array[$y, $y-1] = @$array[$y-1, $y];
}
}
}
}

[...]

I haven't studied the bubble sort algorithm above much, but I'd appreciate
anyone taking the effort to optimize it (as I'm sure it's possible).

Bubble sort? What's to optimize, it's beyond hope

I really don't understand why bubble sort is even studied in CS classes,
except as an example how *not* to do it. It isn't even intuitive...
card players would kill a companion who started sorting a deck using
bubble sort. It may have the occasional application for small lists that
are already almost in order, but otherwise the only thing in its favor
is its pretty name.

That said, your implementation may waste time by looping over the array
after is is already sorted. A flag variable, like the OP used, can help
with that. It's straightforward (untested):

sub bubble_sort {
my $array = shift || [];

for ( my $x = $#$array; $x; $x-- ) {
my $out_of_order;
for ( my $y = 1; $y <= $x; $y++ ) {
if ( $array->[$y-1] gt $array->[$y] ) {
@$array[$y, $y-1] = @$array[$y-1, $y];
$out_of_order ++;
}
}
last unless $out_of_order;
}
}

Anno

 

[Tassilo v. Parseval]

Also sprach Anno Siegel:

[bubble sort]

tried to write a bubble sort function a few months after I started
learning Perl, and I ended up with something like this (untested):

sub bubble_sort {
my $array = shift || [];

for ( my $x = $#$array; $x; $x-- ) {
for ( my $y = 1; $y <= $x; $y++ ) {
if ( $array->[$y-1] gt $array->[$y] ) {
@$array[$y, $y-1] = @$array[$y-1, $y];
}
}
}
}

[...]

I haven't studied the bubble sort algorithm above much, but I'd appreciate
anyone taking the effort to optimize it (as I'm sure it's possible).

Bubble sort? What's to optimize, it's beyond hope

I really don't understand why bubble sort is even studied in CS classes,
except as an example how *not* to do it. It isn't even intuitive...
card players would kill a companion who started sorting a deck using
bubble sort. It may have the occasional application for small lists that
are already almost in order, but otherwise the only thing in its favor
is its pretty name.

There are some derivations of bubble-sort that perform better. I
remember years ago in an exam I was presented with shakersort that
essentially doesn't go stupidly from left to right in the array but
rather from left to right, right to left, left to right, etc., each time
making the array to iterate over smaller at one end.

Of course, it's still not remotely comparable to proper algorithms such
as mergesort or quicksort.

Tassilo

 

[Uri Guttman]

AS> Bubble sort? What's to optimize, it's beyond hope

AS> I really don't understand why bubble sort is even studied in CS
AS> classes, except as an example how *not* to do it. It isn't even
AS> intuitive... card players would kill a companion who started
AS> sorting a deck using bubble sort. It may have the occasional
AS> application for small lists that are already almost in order, but
AS> otherwise the only thing in its favor is its pretty name.

it is taught in CS classes as a classic O(N^2) sort. and for real world
short lists it is usually the fastest sort as it has no setup
overhead. but short can mean as little as 5 elements. is it also the
simplest sort code around (if done well) so it is good to teach for
concepts and such. of course no decent sized sort should use it but it
is a still a required tool to know.

uri

 

[John W. Kennedy]

I really don't understand why bubble sort is even studied in CS classes,

Because it's comprehensible to beginners, and, once understood, can be
built on to explain how to do it better.

(Human beings normally sort using algorithms optimized for compare
operations that are ten to thirty times faster than any manipulation,
and in which the equivalent of PERL's "splice" function is less
expensive than a two-item swap, so human experience isn't of much use.)

For the same reason, when I explain external sorts, I start with the
balanced tape sort algorithm, and build up to the sophisticated (and
often proprietary) algorithms used on modern mainframes.

--
John W. Kennedy
"But now is a new thing which is very old--
that the rich make themselves richer and not poorer,
which is the true Gospel, for the poor's sake."
-- Charles Williams. "Judgement at Chelmsford"

 

[Mark Jason Dominus]

I really don't understand why bubble sort is even studied in CS classes,
except as an example how *not* to do it. It isn't even intuitive...

I seem to recall that Knuth makes the same point, perhaps in _The Art
of Computer Programming_ volume III.

Selection sort is easier to understand, simpler to implement, and
faster to run.

It seems to me that a lot of the traditional material of the computer
science curriculum is similarly useless. For example, in a typical
data structures class one spends a lot of time on complicated
self-balancing tree algorithms, which are of little use, and little
time on hashing algorithms, which are much more valuable.