Slashdot Mirror
The World of YouTube Bubble Sort Algorithm Dancing
theodp writes In addition to The Ghost of Steve Jobs, The Codecracker, a remix of 'The Nutcracker' performed by Silicon Valley's all-girl Castilleja School during Computer Science Education Week earlier this month featured a Bubble Sort Dance. Bubble Sort dancing, it turns out, is more popular than one might imagine. Search YouTube, for example, and you'll find students from the University of Rochester to Osmania University dancing to sort algorithms. Are you a fan of Hungarian folk-dancing? Well there's a very professionally-done Bubble Sort Dance for you! Indeed, well-meaning CS teachers are pushing kids to Bubble Sort Dance to hits like Beauty and a Beat, Roar, Gentleman, Heartbeat, Under the Sea, as well as other music.
A key part of all database systems is the fact that you can ask for a sort order without having to write a sort program. While simple sorts can move quickly, a bubble sort can move even faster. When you're dealing with a multimillion record table, this saves minutes and power per query.
Everybody develops Bubble Sort the same way, proving it's an eventual discovery that no longer qualifies for patents. Teaching it is a basic way of showing the programming language's loop terms and variable scopes, so it's an elementary program to write.
I guess this dance is reminding us that Bubble Sort can be applied to dating. If the girls rank themselves correctly, it takes a bunch of "go over there..." dates in order to get it right.
I agree on Bubb..I mean, BS. But Selection Sort is really only useful with big objects that you don't want to move much. These days everything's a Reference, so it doesn't matter so much. It makes for a really boring dance, too.
Insertion Sort is more useful in modern use cases. If something's "almost sorted" it's very quick.
Shell sort might be even better. It's practically identical to Insertion Sort except only subsets of dancers would step out at one time. And, with a good gap sequence, it gets done much quicker than either of the above.
(T>t && O(n)--) == sqrt(666)
I don't think we should be teaching our kids exponential running time O(n^2) algorithms.
Call me liberal, but I don't think we should be teaching our kids improper definitions for "exponential" *or* myths that O(n^2) algorithms like bubble sort are bad.
Quick: which is going to be faster to sort a list of 4 items, bubble sort or randomized partition merge sort? What's that you say? Proper algorithm selection requires more than knee-jerk application of platitudes? Exactly.
Hang on..
Are you seriously suggesting that bubble sort is useful for N in the millions?
Can you be Even More Awesome?!
They didn't even have a pole. Just what are they teaching women about how to make money these days?
I expect to be downmodded to the lowest level of turtles, but I think it is the idea of since today, dancing is quite popular, and that if they can get young girls to think that programmers dance all day, they might decide to become programmers.
I mean Beyonce is a programmer right?
The shepherds did so well protecting the flock that the sheep no longer believed that wolves existed.
...than as a sorting algorithm!
Believe it or not, but bubble sort really is used in the real world, and not because of incompetence.
Now, maybe it isn't used for most cases, but it is far from being worthless. There are situations where it's really the most optimal algorithm to run, mostly where you are both space constrained (so can't afford the extra memory to allocate more than the list to be sorted), and when you want a low number of instructions to run (because there is no other algorithm which can be performed with as few instructions as you have with bubble sort, and no, abacus sort doesn't count, as you're essentially implementing a specialized piece of hardware to do the sorting for you), but won't use a large data set in the mean time (let's say, less than 100 items, if I recall correctly, but it might be something like 10 or so, which, after that point, the extra instruction overhead in the other algorithms doesn't matter). For instance, one useful place for bubble sorts is in some drivers which need to sort integers, but which don't have a lot to sort, and which using a more complex algoritm would impair their runtime speed. With the right data set, bubble sort ends up being the most optimal algorithm for them to use, ironically.
You just forget that when we say an algorithm is O(n^2) or whatever, that we're discarding insignificant terms which don't contribute to its long term growth, because most of the time, those terms don't really matter. We don't teach any algorithms in computer science classes that are worthless to know. You just need to know when it's appropriate to use what and when, and by simply discarding bubble sort, you're kind of showing that you don't really know that, and are cargo cult programming here.
And more important than average efficiency, shell sort makes better dances!
It's usually mentioned in CS courses because the first stage in introducing these classes is "think about sorting some numbers - how do you go about doing it", and generally Bubble Sort is the first formalisation that falls out of that. The fact that Selection Sort is the one that you think of is neither here nor there - most students come up with something looking like bubble sort.
No one in their right mind would implement quick sort to sort millions of database entries either though. They'd likely implement something like merge sort.
It entirely depends on the order of data in the database. If you know the data is already mostly sorted, then it can perform much better than other methods.
Sleep your way to a whiter smile...date a dentist!
Umm ... (+1, Funny) ... I hope?
Neither of those sorting algorithms is particularly good, but random sort (bogosort) is hilariously bad.
vi ~/.emacs # I'm probably going to Hell for this.
Well, the problem with QuickSort is that if you're unlucky with your pivot choice you can get O(n^2) runtime. The problem with MergeSort is that you have to copy the array, which, for n in the millions, could be an issue.
For such a case I would recommend heapsort or introsort (which is just "quicksort unless I'm getting unlucky, then I do heapsort instead").
HeapSort doesn't get enough love :(
vi ~/.emacs # I'm probably going to Hell for this.
You are correct. But there is a much more direct answer to defend Bubble Sort.
In the real world, i.e. on real hardware, bubble sort usually faster than other algorithms for small data sets. This is due to cache locality. A cache miss can mean the difference between 4 clock cycles vs. over 400 cycles, simply waiting for 4 little bytes to be read from RAM.
Cache misses are now the biggest problem for high performance programming. For instance, (good) video game programmers are very aware of this fact.
Teaching algorithms separately from data structures is one of the biggest flaws in modern computer science education. It's impossible to reason sensibly about one without the other.
I am TheRaven on Soylent News
As others have said, bubble sort is efficient on mostly-sorted datasets. Bubbling sorting your database after every X insertions (for some value of X) or before a search (whichever comes first) makes the world a nicer place.
Got them moderator blues I blieve I walk out the do', With these mod-points I been gettin', I 'most never post no mo'
FYI O(n^2) is called quadratic complexity/time, O(n^3) is cubic, O(n^1) is linear and O(n^0) = O(1) is constant.
Exponential complexity would be O(c^n), where c is a constant.