Bubble sorts have their place (was: FLUKE?

From: Christopher Smith <csmith_at_amdocs.com>
Date: Tue Dec 4 10:17:51 2001

> -----Original Message-----
> From: Fred Cisin (XenoSoft) [mailto:cisin_at_xenosoft.com]

> And I've seen bubble sorts used when they were inappropriate, or worse
> yet, a bubble sort going from left to right, when right to
> left was called
> for - that creates the worst case scenario that gives a
> bubble sort its
> bad reputation.

Back to the description of the bubble sort that Wirth had in his book (the
book is "algorighms + data structures = programs," for the curious), he
suggests modifications to a bubble sort:

Always remember the position of the last switch that you've made. You can
start/end here next time. (A similar thing was mentioned in a previous mail
by somebody)

Alternate the order of the sort going right-to-left one pass and
left-to-right the next. That takes advantage of the fact that a number
that's incredibly far out of place will tend to move further if you're
sorting towards its proper place. (In other words, it's as you say, but
assuming that we don't know the order of the data, so the sort can be
generic and still be more efficient)

Regards,

Chris


Christopher Smith, Perl Developer
Amdocs - Champaign, IL

/usr/bin/perl -e '
print((~"\x95\xc4\xe3"^"Just Another Perl Hacker.")."\x08!\n");
'
 
Received on Tue Dec 04 2001 - 10:17:51 GMT