The stupid question is the question not asked PerlMonks

Re: Re: An informal introduction to O(N) notation

by demerphq (Chancellor)
 on Jan 21, 2003 at 14:02 UTC ( #228679=note: print w/ replies, xml ) Need Help??

It should be noted that many algorithm's O time can be reduced.

True. But then it isnt the same algorithm. :-) Also care in implementation can make one version of an algorithm outperform another. For instance I think you will find that

```my \$tmp;
for my \$i (0..\$#a-1) {
# looping over already-sorted items is not needed
for (0..\$#a-1-\$i) {
if (\$a[\$_+1] < \$a[\$_]) {
\$tmp=\$a[\$_];
\$a[\$_]=\$a[\$_+1];
\$a[\$_+1]=\$tmp;
}
}

}
Is slightly faster than your version. :-) Its funny actually but Knuth discusses this exact issue as a justification as to why he used MIX instead of a high level programming language. People have a tendency to write code in as few characters as possible. (Perl gives an opportunity to take this way beyond reasonable so we can ignore that stuff.) However very often the constructs that take the least space for the human result in the most code being excuted. To take this further for a while I was working on implementing a bunch of the AoP algorithms in perl. Some of them are not feasable as perl doesnt allow low enough operations. I believe that you will find one of the linear search algorthms (you'd never think this would be tricky) is unimplementable in perl to be more efficient than the others (even though in MIX and assembler it is).

Also IIRC the following minor change makes Bubblesort get even faster

```my \$tmp;
my \$swapped;
for my \$i (0..\$#a-1) {
\$swapped=0;
# looping over already-sorted items is not needed
for (0..\$#a-1-\$i) {
if (\$a[\$_+1] < \$a[\$_]) {
\$tmp=\$a[\$_];
\$a[\$_]=\$a[\$_+1];
\$a[\$_+1]=\$tmp;
\$swapped=1;
}
}
last unless \$swapped;
}
As it allows it to bail once the list is sorted. (Atually you could probably be clever and not use one of the extra variables, although only if undef isnt legal in the data being sorted.)

update fixed typo in the second version. thanks jryan. :-)

--- demerphq
my friends call me, usually because I'm late....

Comment on Re: Re: An informal introduction to O(N) notation
Reaped: Re^3: An informal introduction to O(N) notation
by NodeReaper (Curate) on Jan 01, 2009 at 02:30 UTC

Create A New User
Node Status?
node history
Node Type: note [id://228679]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (11)
As of 2013-12-07 19:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?