|
My understanding is that obviously the divide & conquer sorting algorithms of O( n log n ) are far better than the ones of O( n^2 ), except for the case of a small size of data, in which insertion sort is used, as even it is is better than bubble sort.
But it was my experience learning BASIC and then later FORTRAN that bubble sort was introduced as a "read & type in" algorithm. (It was only later when I studied C that I learned about these far better sort algorithms.) So I wonder why is bubble sort even taught? The only explanation I can come up with is that is only a few lines long, with a double for loop (i.e., a very elementary CS concept), so it is easy to "plug & chug" into a program that requires it, without going into the theory of sorting algorithms - and as well would have been useful in the days of the small-byte program, when every line of code was valuable.
Is there some use of this that I am missing here? I 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, LOL), using bubble sort saved on tedious typing as well.
|
|
|
|
|
|
No!!! For data size less than 16, a bubble sort is faster. Much less setup overhead. Do the math!
Gus Gustafson
|
|
|
|
|
|
gggustafson wrote: For data size less than 16, a bubble sort is faster. Much less setup overhead. Do the math
This is an assertion for which evidence is thin. For what O(n log n) sorts is this true? My experience with algorithms I have been measuring lately is that for very small n, the performance of sorts is indistinguishable, but not that O(n2) sorts were faster.
|
|
|
|
|
Evidence is not the issue. A computation of the order statistic is sufficient.
Gus Gustafson
|
|
|
|
|
Depends.
It's a good "teaching algorithm" because it's simple to understand, simple to implement, simple to debug - and it's pretty immediate that you can see results. For a new coder, that's good.
Bubble sort is a lot more complex: it uses a large number of concepts as well as memory so it isn't so applicable to learners.
But...bubble sort works, and if you need to sort a small number of items and can't use standard library routines then it's fine, and I have implemented it a number of times in a number of assembly languages.
These days, most people have access to libraries, and don't have to code sort methods anymore!
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
|
|
|
|
|
I asked myself the same questions.
In the very old days when people had to solder together their computers, you got most code from photocopied newsletters and books like this[^].
Typing in your code from all those dubious sources was the way to go and everyone and his dog had to publish an 'optimized' version of bubble sort. I think it has become some kind of tradition or running gag and by the way a metric to identify the members of the 'It's sooooo easy to implement in BASIC' fraction.
The language is JavaScript. that of Mordor, which I will not utter here
This is Javascript. If you put big wheels and a racing stripe on a golf cart, it's still a f***ing golf cart.
"I don't know, extraterrestrial?"
"You mean like from space?"
"No, from Canada."
If software development were a circus, we would all be the clowns.
|
|
|
|
|
|
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 ...)
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
