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.
i guess its similar to the way logarithms are taught where you spend like 3 days learning how to deal with random bases when only 2 are normally actually used.
and Bubble Sort actually has a defined endpoint unlike say Random Sort
I don't think we should be teaching our kids exponential running time O(n^2) algorithms. Randomized partitioned merge sort theta(n lg n). Sure, bubble sorts seem harmless today, it leads to criminal token rings.
Slashdot's rate-of-post filter: Preventing you from posting too many great ideas at once.
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.
Yep, Random Sort is subject to bad draws of randomness that cause it to randomly walk to a longer solution. A combo technique of random sort somewhat, then bubble sort is often effective.
While I don't disagree with your overall point, if it's not obvious to a CS student why a bubble sort works after a moment of thought, they're in the wrong field.
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)
When you're dealing with a multimillion record table, this saves minutes and power per query.
What database are you using? Sqlite? OpenOffice Base?
lucm, indeed.
Hang on..
Are you seriously suggesting that bubble sort is useful for N in the millions?
Can you be Even More Awesome?!
I'll be impressed when they dance a quicksort to Flight of the Bumblebee.
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!
But it's web scale! ;)
putting the 'B' in LGBTQ+
Shell sort was always my favorite in terms of elegance, IMO
putting the 'B' in LGBTQ+
And more important than average efficiency, shell sort makes better dances!
I think The New Guy confused Bubble Sort with Quicksort. When you have been out of academia for a while, it is easy to get the names mixed up.
In the modern server computing environment, it is extremely rare that anyone needs to choose a specific sort algorithm. It is far more important to know when and what to sort than it is to tweak the algorithm's details.
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.
A _proof_ that bubble sort works is actually pretty hard to construct.
There is absolutely no reason to teach bubble sort. Insertion sort should be the first one to be taught.
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.
I wish score +1 Awesome existed. Ah well, +1 insightful will hove to do.
I disagree. The simplest idea that comes naturally and logically is to first find the smallest number and put it first, then find the next larger number and put it after, and repeat. Swapping adjacent items over, and over, and over again, is a much more systematic and "invented" approach, and not at all a natural way of going about it.
Or 3...
(10, 2, e)
Hang on..
Are you seriously suggesting that bubble sort is useful for N in the millions?
The GP must be the database guy they hired for the Russian stock market.
Bubblesort has two advantages. The first is that, because it's only swapping adjacent elements, it has very good locality of reference (which means better cache usage, but can also mean more amenable to fine-grained locking). The second is that it performs well on almost-sorted data (that O(n^2) is the worst case - it's closer to O(n) if your inputs are mostly sorted). These two mean that there are situations where bubblesort can be useful, though they're quite rare.
I am TheRaven on Soylent News
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
That's only if you don't have the requirement to sort in place. Bubblesort is also a good way of getting students to start thinking in terms of induction. Each step in the bubblesort leaves the array more sorted than it was before.
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'
I don't understand why Bubble-Sort is even mentioned in CS courses. It is not immediately apparent to new students why repeatedly swapping adjacent items in this manner eventually results in a sorted list. With Selection-Sort on the other hand it is immediately clear why it works, and it is also faster than Bubble-Sort, and appropriate to use in simpler cases.
Bubble-Sort is a bogus algorithm and should not be mentioned nor taught to new students, and henceforth it should be shortened and known as BS, because that's exactly what it is.
The bubble sort algorithm is the easiest sorting method for most beginning computer science and programming students to comprehend. Next you will be suggesting they be taught the radix sort algorithm as their first assignment. It is the same nonsense I hear from supposedly experienced programmers when they claim BASIC is a terrible introductory language to teach basic programming concepts. The personal computer industry and much of modern software has been developed by hobbyist programmers who taught themselves BASIC on their 8-bit computers. The trash that is modern-day programming in the form of "design patterns", "unit tests", "frameworks" obsessed hipsters and their clueless managers is a bane on the profession.
I remember coding these sorting algorithms in 6502 assembly language on a Commodore VIC-20 in the early 1980s. Those were the good years.
A _proof_ that bubble sort works is actually pretty hard to construct.
There is absolutely no reason to teach bubble sort. Insertion sort should be the first one to be taught.
Insertion sort might be misconstrued as sexual harassment by the radical feminist computer science students and faculty.
CAPTCHA: disgusts
Mostly I just set up a weekly job to ALTER INDEX {index_name} ON {table_name} REBUILD. Overnight between Saturday and Sunday is usually a good time to do this.
How the DBMS gets that job done is Not My Problem(tm), just as long as it works.
(Obviously I mean updates, not insertions.)
Got them moderator blues I blieve I walk out the do', With these mod-points I been gettin', I 'most never post no mo'
The best solution is always dependent on the task and the dataset.
Got them moderator blues I blieve I walk out the do', With these mod-points I been gettin', I 'most never post no mo'
...With Selection-Sort on the other hand it is immediately clear why it works, and it is also faster than Bubble-Sort, and appropriate to use in simpler cases.
Sure, but can the kids dance to it?
Dark Reflection
If I believe the data is going to already be mostly sorted why wouldn't I just use insertion sort?
Bubble sort (and similiars like insertion sort) is ok for starting an introductory course. Next lesson, you tell them you have something remarkably better, and show them the nlogn sorting algorithms. And how they are awesomely faster for sorting a few million items.
As for basic, it is a waste-of-time introductory language. Those who made it after starting with basic, made it because they managed to unlearn basic and move on to something better. (I am guilty of going that way - even 6510 assembly were more useful than basic.) Talented programmers don't need basic - other than to get them interested in computers in the first place. But if your'e going to teach, just skip basic. "The best language" is another debate, but surely a more typed language, with actual compilers would be useful . . .
Basic is only for those who aren't going to go beyond basic anyway. If their ambition merely is to code word macros - basic is for them. Can't call them programmers though...
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.
Most people get to insertion sort or bucket sort first, since those are the ones that arise naturally from sorting playing cards in respectively your hand or the whole deck on the table.
MS Access.
It's not always the best program for databases, but it has the easiest to use UI. Visual Basic 6 and VBA are almost interchangeable.
This is a great dilemma that database engines deal with. With all of the sorting programs possible, which is the one that will solve it the fastest? There's not much of a chance for figuring it out on the first pass... you'd have to sort the database using all the sorts to get times, and that's wasted work. Database engines have some logic to say which they should guess is right the first time, and then if the query is asked for again it can rely on cache or place only the new records into the list.
This is why a database programmer should recalc his test data frequently, it's going to help the live system know where to start.
I sent the Hungarian dance link to my Magyar uncle who is somewhat computer illiterate. This'll show him how binary can solve simple order.
Don't be apathetic. Procrastinate!
OTOH Why not make a dance to visualize code?
Don't be apathetic. Procrastinate!
They did, it's called the 'Fish-Slapping Dance.'
Hmmm... Can you code that for me?
I teach both C and Data Structures. Bubble sort is for my C class where I am trying to make sure the students fully comprehend arrays (most of my students come from a non-existent programming background, and the school isn't sold on my teaching them Python as a first language just yet as apparently I am the only instructor who can use it meaningfully), how indexes work (getting them to reverse an array or a string doesn't quite seem to do it for about half of them), and my better students will have implemented bubble sort on linked lists by the end of the semester, as well. Understanding that bubble sort works isn't a problem for them, but they are only starting to think beyond what a single loop can do algorithmically. I have tried jumping to insertion sort and as a whole there is poor integration of the knowledge to take forward. Good/better/best options just can't happen for most of these students at this point, and so it has to wait for Data Structures where the first sort they learn is Insertion Sort and I don't care which language they use. I guess if someone started using Mindfuck or Ada I might start to care. They add every sort to one big program where they can calculate how much work each sort does and how much system time it takes to operate for randomly generated lists.
As for concerning themselves with cache misses as one person suggested it, until students have a better understanding of systems, that can't be readily done with a class of 40+ frequently unmotivated students (it can with ~10 motivated students, the breakpoint occurring somewhere in the middle, of course), though I start introducing the penalties of register/cache/RAM/disk in this class so that by the time I am teaching embedded systems the students who chose that path usually have a good grasp of it, with the best ones looking even at divide instructions with disdain. With the semester system being what it is, though, teaching all of that as a simultaneous, cohesive chunk of information just isn't going to happen.
while (music_playing())
{
dancer1.slap(dancer2, leftCheek, smallFish);
dancer1.slap(dancer2, rightCheek, smallFish);
dancer1.slap(dancer2, bothCheeks, smallFish);
}
dancer2.slap(dancer1, head, bigFish);