No such thing as a small change PerlMonks

### Comment on

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

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
 [choroba]: beer [choroba]: oh ok [marto]: I crashed the ScotLUG Christmas night, having never actually been to ScotLUG [choroba]: Corion yeah, I probably already told you about how Bjarne Stroustrup was asked whether he still watched the new tech trends and what really impressed him [choroba]: His reply was "I watch them, but I haven't been impressed in the last 10 years. There's been nothing new". That was 2 years ago :) [ambrus]: Ok, the docs is somewhat unclear. It does say that when an object is garbage collected, it will get cleaned up, and eventually can no longer get messages. It's not clear how long this takes, eg. I think it's kept alive until its queued events are handled [ambrus]: in the loop, and I'm not sure if that's ok for AnyEvent. Also, it's not clear if a Timer or File object you free really is garbage collected, i.e. that Prima doesn't keep some references to it, but I hope so. [Corion]: choroba: No, I don't remember that story, but yes, it matches my experience ;)) [ambrus]: Hopefull the object isn't kept alive, the events are processed immediately, but you'd have to read a lot of source code to be sure about that. [Corion]: ambrus: I think both of AnyEvent and Prima are pretty tight in their memory management because they both are cooperative multitasking and (I think) both use the Perl memory management for managing things

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (7)
As of 2016-12-09 10:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
On a regular basis, I'm most likely to spy upon:

Results (150 votes). Check out past polls.