|
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.
|
|
|
|
|
Sorry Emilio, was out on a bender with the Missus last night when you posted this. Don't think alcoholic mist would have been acceptable to her, not a chance for me.
Michael Martin
Australia
"I controlled my laughter and simple said "No,I am very busy,so I can't write any code for you". The moment they heard this all the smiling face turned into a sad looking face and one of them farted. So I had to leave the place as soon as possible."
- Mr.Prakash One Fine Saturday. 24/04/2004
|
|
|
|
|
The
===
The incredible Hulk is green but he's not a Martian feign an injury commersy beat me daddy eight to the bar nonesuch a doofoosballyardboy wonder bread hot from the
|
|
|
|
|
"Beat me daddy"?
Please explain yourself.
|
|
|
|
|
8 to the bar. https://en.wikipedia.org/wiki/Beat_Me_Daddy,_Eight_to_the_Bar[^]
The version I'm familiar with is that by Commander Cody and his Lost Planet Airmen - a great rockabilly/Americana band!
Your understanding these is predicated on having similar life experiences as me; if you were born in the late 1950s, in California, are well-versed in music and popular (especially U.S.) culture and history, you'll probably get most of it.
modified 14-Aug-15 13:20pm.
|
|
|
|