Bubble sort! I stumbled across this clip while looking for video algorithm explanations.

Wow, even Obama knows what’s up. Bubble sort ain’t where it’s at.

The idea behind bubble sort is that given an array, you can go through the array, item by item, and compare each item with the item that is next in line. If the first item is larger (or comes after) the second item, then you should swap the pair. Continue these pair comparisons until you get to the end and then repeat. After enough times running through the array, you will come to the point where the array is sorted, and you’ll find that you’ve made no swaps.

There are some advantages to bubble sort. It’s easy to understand how it works. It uses up a constant amount of auxiliary space, it’s stable, and in the best case scenario, when the array is already sorted, it takes linear time.

Alas, bubble sort is mostly impractical. In application, bubble sort can take O(n^2). Not great.

Here’s my implementation of bubble sort in ruby. It’s really all about that swap flag.

** EDIT : After some thinking, I realized that during each iteration there is no need to check the items at the end since the largest item will “bubble up” to the top. The subarray that you are looping through will get smaller & smaller. This can be accomplished by iterating backwards over the array and decreasing the area searched, but I haven’t added this yet. Surprisingly, Bubble Sort could be a little less terrible.