This is marginally away from the submitter's question, but it warrnats attention:
The sad truth is that, as far as optimization goes, this isn't where attention is most needed.
Before we start worrying about things like saving two cycles here and there, we need to start teaching people how to select the proper algorithm for the task at hand.
There are too many programmers who spend hours turning their code into unreadable mush for the sake of squeezing a few milliseconds out of a loop that runs on the orde
by Anonymous Coward writes:
on Friday February 25, 2005 @05:00PM (#11781401)
Heh. Wasn't that long ago that every other guy's homegrown 3D engine (software rendering, mind you, this was the 100mhz pentium era) had an ultra-optimized version of bubblesort doing the depth sorting of polygons in a painter's algorithm type affair.
I certainly hope those people are better educated these days.
Wasn't that long ago that every other guy's homegrown 3D engine (software rendering, mind you, this was the 100mhz pentium era) had an ultra-optimized version of bubblesort doing the depth sorting of polygons in a painter's algorithm type affair.
I certainly hope those people are better educated these days.
It's almost impossible to beat an optimised assembly bubble-sort when sorting small data sets (up to hundreds, sometimes even thousands). It takes a while for better algorithmic performance to overcom
Heap sort can be worth it if you don't need all of the elements to be sorted. For example, say you wanted only the smallest 1% of elements from an array sorted.
A heap can be constructed in linear time, but extracting each next smallest element takes log time. Hence, getting the m smallest/largest elements out of an array of n elements takes O(n + m log n). If m is small, we're talking linear sorting time wrt to the total size overall. If n = m, the whole thing becomes O(n log n), which is the provably
If n = m, the whole thing becomes O(n log n), which is the provably lowest bound on sorting any ordered sequence.
For sorting on a computer, yes. However, it's easy to construct a gedanken-experiment demonstrating an O(n) sort algorithm. Take a number of thin rods (the demonstration used dry spaghetti) equal to the number of values to be sorted, and cut the rods in lengths proportional to the values. Sweep all the rods together into a single bundle, and whack one end on a tabletop to align that end. As lo
Grrr, you named the algorithm that must not be named! Cursed be the name of the fool who thought it would be a good algorithm for introductory students - I've lost count of the number of people convinced that this satan-spawned algorithm is faster than an insertion sort (it's not) and that there's no reason for them to learn to use the qsort() function. N.B., not to implement a quick sort, but to simply call a standard library routine.
The most frustrating thing is that, if you must use the algorithm that must not be named, the bidirectional form of the algorithm is much faster (in practice) than the unidirectional form yet really no more complex to code than the latter if you have any potential as a software developer.
Oh yeah, the details of the bidirectional form....
1) obviously, you go both directions.
2) on the i-th pass, you only need to go to the N - i-th position (or the corresponding positions when headed the other way). Most people forget this nuance of the algorithm.
3) if you're doing a bidirectional sort you can start at the last exchange. You still have to go to the N - i-th position.
The algorithm is still O(n^2), but these simple changes will make the implementation maybe 4x faster.
Oops - forget about that last point. I was thinking about an unrelated algorithm. This is why I always code from CLR, complete with assertions and page references in the comments. It doesn't matter if the algorithm is fast if it's also wrong.
I managed this (bidirectional bubble sort with reducing endpoints) for my first programming exercise in my very first introductory programming class. I was just being a smartass, wanted mine to go faster than everybody else's.
I agree it sorts the men from the boys at that very elementary level, but detecting true programming talent does require a bit more than that. Especially these days when the pool is that much larger.
Hehe.
Heard about bogosort?
Use random permutations and check if you have the data sorted.
The many-worlds version of bogosort is the fastest possible sorting algorithm though. Its O(C). For those that don't know, the many-worlds version just does one random permutation, with a new universe being created for each possible outcome of the permutation. You then destroy all the universes were the dataset isn't sorted.
You then destroy all the universes were the dataset isn't sorted.
Maybe collapse is a better word here? Although this was always the part where my understanding started walking out the door... (ie: wouldn't this experientially be like rolling a couple dice and then exploding my own universe if it didn't come up boxcars?)
My friend used to work at Netscape (way back when they were actually coding their own browser). He said that they discovered the reason that Netscape Navigator 3.x took so long to start up was because it performed a big bubble-sort when initializing the Java plugin. Replacing it with quicksort halved the startup time.
The bubble sort (there! I said it!) is actually very efficient for the case where you know for a fact that you're starting with very-nearly-sorted data. That's the only excuse I can imagine for using it.
I thought it was used as an example of algorithm improvements - see, now you have the quick sort and it runs 5000 tiems as fast. If people are actually teaching that as an algorithm to be used they should be shot, of course.
I have the simplest tastes. I am always satisfied with the best.
-- Oscar Wilde
Algorithms, Not Stupid Processor Tricks (Score:5, Insightful)
The sad truth is that, as far as optimization goes, this isn't where attention is most needed.
Before we start worrying about things like saving two cycles here and there, we need to start teaching people how to select the proper algorithm for the task at hand.
There are too many programmers who spend hours turning their code into unreadable mush for the sake of squeezing a few milliseconds out of a loop that runs on the orde
Re:Algorithms, Not Stupid Processor Tricks (Score:0)
I certainly hope those people are better educated these days.
Re:Algorithms, Not Stupid Processor Tricks (Score:2, Insightful)
I certainly hope those people are better educated these days.
It's almost impossible to beat an optimised assembly bubble-sort when sorting small data sets (up to hundreds, sometimes even thousands). It takes a while for better algorithmic performance to overcom
Re:Algorithms, Not Stupid Processor Tricks (Score:2)
Re:Algorithms, Not Stupid Processor Tricks (Score:1)
Re:Algorithms, Not Stupid Processor Tricks (Score:1, Informative)
Re:Algorithms, Not Stupid Processor Tricks (Score:3, Insightful)
A heap can be constructed in linear time, but extracting each next smallest element takes log time. Hence, getting the m smallest/largest elements out of an array of n elements takes O(n + m log n). If m is small, we're talking linear sorting time wrt to the total size overall. If n = m, the whole thing becomes O(n log n), which is the provably
Re:Algorithms, Not Stupid Processor Tricks (Score:2)
For sorting on a computer, yes. However, it's easy to construct a gedanken-experiment demonstrating an O(n) sort algorithm. Take a number of thin rods (the demonstration used dry spaghetti) equal to the number of values to be sorted, and cut the rods in lengths proportional to the values. Sweep all the rods together into a single bundle, and whack one end on a tabletop to align that end. As lo
The algorithm that must not be named! (Score:5, Funny)
The most frustrating thing is that, if you must use the algorithm that must not be named, the bidirectional form of the algorithm is much faster (in practice) than the unidirectional form yet really no more complex to code than the latter if you have any potential as a software developer.
Re:The algorithm that must not be named! (Score:2)
1) obviously, you go both directions.
2) on the i-th pass, you only need to go to the N - i-th position (or the corresponding positions when headed the other way). Most people forget this nuance of the algorithm.
3) if you're doing a bidirectional sort you can start at the last exchange. You still have to go to the N - i-th position.
The algorithm is still O(n^2), but these simple changes will make the implementation maybe 4x faster.
(correction) (Score:2)
yes but (Score:2)
Re:The algorithm that must not be named! (Score:2)
I agree it sorts the men from the boys at that very elementary level, but detecting true programming talent does require a bit more than that. Especially these days when the pool is that much larger.
Re:The algorithm that must not be named! (Score:4, Funny)
The many-worlds version of bogosort is the fastest possible sorting algorithm though. Its O(C). For those that don't know, the many-worlds version just does one random permutation, with a new universe being created for each possible outcome of the permutation. You then destroy all the universes were the dataset isn't sorted.
Re:The algorithm that must not be named! (Score:2)
You then destroy all the universes were the dataset isn't sorted.
Maybe collapse is a better word here? Although this was always the part where my understanding started walking out the door... (ie: wouldn't this experientially be like rolling a couple dice and then exploding my own universe if it didn't come up boxcars?)
Re:The algorithm that must not be named! (Score:3, Funny)
The programmer will be alive in the universes which bogosort worked well.
Re:The algorithm that must not be named! (Score:1)
Re:The algorithm that must not be named! (Score:1, Informative)
Re:The algorithm that must not be named! (Score:2)
Re:The algorithm that must not be named! (Score:2)
Re:The algorithm that must not be named! (Score:3, Insightful)
Re:The algorithm that must not be named! (Score:2)
Let's not be prejudiced. Bubblesort is often faster than the fancier algorithms on "small" datasets.
Re:The algorithm that must not be named! (Score:2)