Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much

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??

in reply to Re: An informal introduction to O(N) notation
in thread An informal introduction to O(N) notation

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....

Replies are listed 'Best First'.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://228679]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (7)
As of 2017-06-25 16:12 GMT
Find Nodes?
    Voting Booth?
    How many monitors do you use while coding?

    Results (568 votes). Check out past polls.