|
|
There is nothing wrong with using a simple algorithm that you understand and that is adequate to the task. It sometimes easier to write a simple bubble sort than to do the work of interfacing with a library function.
|
|
|
|
|
Not all people in this world are computer scientists. There are different mortals like me whose formal education is in mechanical engineering.
For us, things need to be simple and 'relatable'. Bubble sort is great in these respects. Analogous to the evolution of machines, where they started with simple workable stuff, and gradually increased the efficiency.
Understanding a subject from a historical, evolutionary perspective is likely to give a better insight into how things work.
|
|
|
|
|
Your definitely on to something. A while back I read great series of articles about this at Dr. Dobb's magazine.
Andrew Koenig on Dr. Dobb's Journal discussed this exact subject.
There are a series of articles starting with this one on why bubble sort is slow, but often used...
http://www.drdobbs.com/cpp/teaching-c-badly-how-to-sort-slowly/229625601[^]
http://www.drdobbs.com/cpp/more-thoughts-on-sorting/229700303[^]
The main point being:
"Students tend to use the first technique they learn long after they should have outgrown it."
The Right Way To Teach Sorting - Dr. Dobb's mag[^]
Teaching using bubble sort now is really a hold-over from times past.
Now, there are built in algorithms that do the work much more efficiently.
Basically, he mentions that often programmer's learn the bubble sort first and then don't go on to learn better ways so it can cause issues. He says, teach the use of the built-in algorithms and then teach how the algorithms are written.
|
|
|
|
|
Bubble sort is kinda bad even for an O(n²) algorithm. It's not the shortest code, not the easiest to understand, not even the fastest on average quadratic time sorting algorithm. As far as I can tell the only thing it has going for it is that it's the most popular one.
Combsort is a large improvement over bubble sort, but still small code.
Shellsort deserves to be more widely known even though it isn't optimal, because it's the simplest way to get a worst case better than quadratic.
If you're going to learn a "dumb sort" anyway, learn insertion sort - you will actually use it someday.
|
|
|
|
|
Of course the way BS (don't excuse that pun) uses to test if two items needs swapping is still the fastest way to test if a list is already sorted.
I can only think of one sort of scenario (other than very small lists/arrays where it may or may not perform faster than insertion sort): When sorting directly on a sequential streaming media (such as a tape drive) with too little RAM/Secondary (random access) storage to enable reading the entire contents at once.
swampwiz wrote: So I wonder why is bubble sort even taught?
Mainly as a means to introduce the thought processes around algorithmic optimizations, not so much to teach "a sorting algorithm", but rather to teach how to recognise stuff such as O(N), O(log N), O(N logl N), O(N^2), etc... It's very simple to understand and implement, while some of the divide-n-conquer stuff is pretty complex (especially for beginners).
|
|
|
|
|
swampwiz wrote: suppose that back in the quaint days of "book distribution" (i.e., the only inexpensive way to transfer program code was to put it in a book and have the user type it in
No, it was always a poor example of a sort algorithm, even in the memory constrained days, and was always presented as such in my experience. It was, however, a good introduction to nested loops, algorithm analysis, and, oh yes, concepts of sorting.
Most discussions, especially the algorithm analysis ones, ended with a discussion of how insertion sort was much better, and that quicksort was even better if you could keep the entire dataset in memory and could afford the complexity.
We can program with only 1's, but if all you've got are zeros, you've got nothing.
|
|
|
|
|
There's a good reason to teach bubble sort: don't turn out graduates who don't know what bubble sort is!
Old timers and interviewers would think, "Good Lord, newbies these days don't even know bubble sort. We're doomed!"
They will never have seen anything like us them there. - M. Spirito
|
|
|
|
|
Bubble sort is useful in teaching because it gives you a baseline to compare other sorts with. It is also fairly easy to analyse for complexity which also makes it a good teaching case.
In the real world there are also good uses for bubble sort. In computer graphics transparent objects must be rendered back to front in order to get proper compostion of the surfaces, so you have to sort them. If you are doing real-time graphics then you have to sort each frame. Since the camera moves relatively little each frame, most of the time the sort order doesn't change. A bubble sort can detect this on it's first pass and early-out. This makes the perf O(n). Additionally when objects do end up out of order due to their movement or the camera's, the change in the ordering is very localized, ie things just tend to swap with their neighbors in the sorted list. Here again, a bubble sort can do a couple of passes and then detect that it's done and exit. Any time you have a sorted or nearly sorted list bubble sort can generally do a good job with it.
|
|
|
|
|
"Is there some use of this that I am missing here?"
It's an example of the worst algorithm of its class.
|
|
|
|
|
Ok, I have to admit I do not know Azure ML really. I am about to discover it. 
modified 19-Jan-21 21:04pm.
|
|
|
|
|
I make all my major life choices using a magic 8 ball.
|
|
|
|
|
Only serious replies allowed
modified 19-Jan-21 21:04pm.
|
|
|
|
|
0x01AA wrote: Only serious replies allowed
Unfortunately, my good chap, there is not a serious bone in my body. Cheerio! 
|
|
|
|
|
Quote: Only serious replies allowed
In the Lounge?? You gotta be kidding!
How do we preserve the wisdom men will need,
when their violent passions are spent?
- The Lost Horizon
|
|
|
|
|
And why do you think, I tag  ged it as joke?
modified 19-Jan-21 21:04pm.
|
|
|
|
|
Emilio Largo wrote: I make all my major life choices using a magic 8 ball.
Hey #2, I use an icosahedral die (whilst I stroke my white cat ...)
|
|
|
|
|
|
Which one? Peaaaassseeee ?
[Edit]
Here the missing 'l' 
modified 19-Jan-21 21:04pm.
|
|
|
|
|
Data.
You cannot learn what is genuinely random - but once you get started with ML you will be amazed at what you find is not as random as you had thought.
|
|
|
|
|
|
|
Emilio Largo wrote: An hour == One drink on average
Why so low? 
The United States invariably does the right thing, after having exhausted every other alternative. -Winston Churchill
America is the only country that went from barbarism to decadence without civilization in between. -Oscar Wilde
Wow, even the French showed a little more spine than that before they got their sh*t pushed in.[^] -Colin Mullikin
|
|
|
|
|
You have to inhale vapor in the bar for a whole hour to get drunk? I don't think Nagy has the patience!
How do we preserve the wisdom men will need,
when their violent passions are spent?
- The Lost Horizon
modified 14-Aug-15 17:05pm.
|
|
|
|
|
Cornelius Henning wrote: I don't Nagy has the patience!
Yeah, he might not, but he could get some exercise, I guess...walking around the bar, sippin' the vapor.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
