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.

Re:

[laurencetux]

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

Re:

[The New Guy 2.0]

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.

Re:

[linuxrocks123]

Umm ... (+1, Funny) ... I hope?

Neither of those sorting algorithms is particularly good, but random sort (bogosort) is hilariously bad.

Re:Bogus algorithm

[The New Guy 2.0]

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.

Re:

[lucm]

When you're dealing with a multimillion record table, this saves minutes and power per query.

What database are you using? Sqlite? OpenOffice Base?

Re:

[The New Guy 2.0]

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.

Re:Bogus algorithm

[zippthorne]

Hang on..

Are you seriously suggesting that bubble sort is useful for N in the millions?

Re:

[plopez]

But it's web scale! ;)

Re:

[Anonymous Coward]

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.

Re:Bogus algorithm

[beelsebob]

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.

Re:

[linuxrocks123]

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 :(

Re:Bogus algorithm

[Half-pint HAL]

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.

Re:

[Anonymous Coward]

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.

Re:

[Half-pint HAL]

The best solution is always dependent on the task and the dataset.

Re:

[Half-pint HAL]

(Obviously I mean updates, not insertions.)

Re:

[The New Guy 2.0]

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

Re:Bogus algorithm

[davester666]

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.

If data is mostly sorted why not insertion sort?

[Sits]

If I believe the data is going to already be mostly sorted why wouldn't I just use insertion sort?

Re:

[InfiniteLoopCounter]

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.

Re:

[TheRaven64]

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.

Re:

[Anonymous Coward]

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.

Re:Bogus algorithm

[Ken_g6]

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 [wikipedia.org] 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.

Re:

[plopez]

Shell sort was always my favorite in terms of elegance, IMO

Re:Bogus algorithm

[xvan]

And more important than average efficiency, shell sort [youtube.com] makes better dances!

Re:

[TheRaven64]

Insertion sort is one of these good-on-paper algorithms. It's very fast if insertion is cheap. But insertion relies copying unless your data structure is a linked list. If it's an array (worse, a contiguous on-disk store) then that copying can be very expensive. If it is a linked list, then you're going to have very expensive search (sure, you may still be O(log(n)), but that constant multiple is going to be hurt by the fact that you're hammering your cache and killing your branch predictor).

Teaching

Re:Bogus algorithm

[beelsebob]

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.

Re:

[TheRaven64]

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.

Re:

[Carewolf]

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.

Re:

[QQBoss]

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 impleme

Re:

[Anonymous Coward]

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 themse

Re:

[OakDragon]

...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?

Call me conervative, but

[scorp1us]

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.

Re:Call me conervative, but

[stoploss]

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.

Re:

[plopez]

I would just skip the sort and do a linear search. As a matter of fact I *am* that lazy.

Re:

[Anonymous Coward]

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 instructio

Re:

[TheRaven64]

Insertion sort is terrible for the use cases the grandparent described. For one thing, it requires allocating a new data structure for storing the data (an immediate disqualification for a lot of embedded tasks). Second, it has much worse cache interaction because it requires searching the second array. Assuming that your target is an array, then it also requires a bit memcpy for each insert, which means that it likely requires a similar number of memory operations to the bubblesort, but with more tempor

Re:

[Half-pint HAL]

Actually, insertion sort can be done with a single array structure. When you insert a value into the new list, you delete it from the old list. So the total len(old) + len(new) = len(original). You can use a single int to identify the partition between the segment of the array that represents the new list and the segment that represents the new, sorted list, and effectively do sort-in-place. Hell, it's not even an extra variable, as you would need that index to keep track of the next element to add to the n

Re:

[dottrap]

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.

Re:

[Anonymous Coward]

Working with these algorithms exercises the brain. The benefit is not just having the knowledge, but having the mental ability to understand a complex novel problem and implement an optimal solution to it.

I have interviewed many (and worked with a few) self-taught programmers who skipped all that "already solved" stuff and usually just hit the Internet to find ready-made solutions to their problems. There were many simple things they could do well. But once in a while a problem required the building of a

Re:

[rasmusbr]

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.

Re:

[Ol Olsoc]

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?

Re:

[Whiteox]

OTOH Why not make a dance to visualize code?

Not bad, but...

[Len]

I'll be impressed when they dance a quicksort to Flight of the Bumblebee.

Re:

[david_bonn]

I'll be impressed when they dance a quicksort to Flight of the Bumblebee.

Or a merge sort to Aaron Copland's "Fanfare of the Common Man".

More useful as a dance...

[Tony Isaac]

...than as a sorting algorithm!

Excellent visual explanation for non-geeks

[Whiteox]

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.