beanz Magazine

Bubble Sorts

skippyjon on Flickr

With a bubble sort, numbers sort themselves as they bubble to the left of a group of numbers. Here's a fun catchy video to explain.

I came across this wonderfully silly but highly educational video that demonstrates how bubble sorting works in programming and computer science:

Aside from the catchy tune, and fine dancing, you should have an intuitive idea of how bubble sorting works after watching this video.

Naturally, I wondered what bubble sorts really are and what kinds of sorts are available in software programming. And what value does sorting offer?

What Are Bubble Sorts

Think of soup bubbling on a stove. With a bubble sort, numbers sort themselves as they bubble to the left of a group of numbers. The numbers within the group, also called an array, are compared in pairs starting with the first two numbers on the left. The two numbers are compared and swapped if the numbers are in reverse order. So a pair 3 and 2, sorted from lowest number to highest number, would be swapped to create 2 and 3. In this case, the number 2 has bubbled up in the sort order.

Let's say we have an array (a group) of these numbers: 4 3 6 5 2 1. A bubble sort would evaluate this array in groups of two numbers, from lowest number to highest number, like this:

We start with the array 4 3 6 5 2 1.
4 and 3: this pair would swap to become 3 and 4. The array would be 3 4 6 5 2 1.
4 and 6: this pair would not change the order of the array. 4 is a lower number than 6.
6 and 5: this pair would swap to become 5 and 6. The array would be 3 4 5 6 2 1.
6 and 2: this pair would swap to become 2 and 6. The array would be 3 4 5 2 6 1.
6 and 1: this pair would swap to become 1 and 6. The array would be 3 4 5 2 1 6.
Next, having reached the right end of the array, we start again at the far left of this array.
3 and 4: this pair would not change the order of the array.
4 and 5: this pair would not change the order of the array.
5 and 2: this pair would swap to become 2 and 5. The array would be 3 4 2 5 1 6.
5 and 1: this pair would swap to become 1 and 5. The array would be 3 4 2 1 5 6.
Next, we start again at the far left of this array.
3 and 4: this pair would not change the order of the array.
4 and 2: this pair would swap to become 2 and 4. The array would be 3 2 4 1 5 6.
4 and 1: this pair would swap to become 1 and 4. The array would be 3 2 1 4 5 6.
4 and 5: this pair would not change the order of the array.
5 and 6: this pair would not change the order of the array.
Next, we start again at the far left of this array.
3 and 2: this pair would swap to become 2 and 3. The array would be 2 3 1 4 5 6.
3 and 1: this pair would swap to become 1 and 3. The array would be 2 1 3 4 5 6.
3 and 4: this pair would not change the order of the array.
4 and 5: this pair would not change the order of the array.
5 and 6: this pair would not change the order of the array.
Next, we start again at the far left of this array.
2 and 1: this pair would swap to become 1 and 2. The array would be sorted: 1 2 3 4 5 6.

Sorting here is based on simple numbers. You can sort based on measurements, for example, short to tall. Or you could sort based on groups of numbers, perhaps telephone area codes. And you can sort alphabetically. In all cases, sorting is simply grouping objects based on a defined order, for example, alphabetically or numerically.

What Other Sorting Methods are Used in Programming?

There are two types of sorting in computer science, internal and external. If the data set can fit the computer memory space, sorting is internal. However, sorting is external if the data set is so large it requires external storage.

Different methods of sorting have different costs in terms of computer memory required to store data as it is evaluated and time spent evaluating each piece of data in a data set.

For example, a bucket sort is a wonderfully simple method to evaluate data. Let's say you have an array, or group, of these numbers: 6, 1, 12, 3, and 5. With a bucket sort, you create a second array with the length of the highest number in your initial array, in this case, 12. Next you assign each number to their respective location in the second array:

1 is placed in the first index spot in the second array.
3 is placed in the third index spot in the second array.
5 is placed in the fifth index spot in the second array.
6 is placed in the sixth index spot in the second array.
12 is placed in the twelth index spot in the second array.

The second array looks like this:

1 null 3 null 5 6 null null null null null 12

This simple approach to sorting almost feels like cheating. It's certainly a quick and elegant solution to sorting an array whose elements may be in chaotic order. It's also possible with many programming languages, to delete the empty (null) index spots in the second array once you place each number from the first array into its numeric spot in the second array. Deleting empty spots in the second array leaves you with a simple sorted list: 1, 3, 5, 6, 12.

There are many other sorting strategies used in computer science and software programming. The Learn More links below describe other sorting options. And I plan to write more about sorting in future issues of this magazine.

What is the Value of Sorting?

Sorting helps manage data, especially large amounts of data. Let's say you want to look up all students whose first name is Albert. If you do not sort your list of student names first, every time you search for the name Albert you will have to evaluate every name in your list. However, if you first sort all names alphabetically, your search can quickly eliminate all names that do not begin with the letter A, then names that do not begin with Al, and so on until you isolate (sort) all students whose first name is Albert. In this example, sorting is a strategy to save time and resources spent evaluating data to find all instances of the data requested.

Learn More

Bubble Sort as a Hungarian Folk Dance

http://geekdad.com/2013/08/bubble-sort-as-a-hungarian-folk-dance/
http://memolition.com/2013/08/13/bubble-sort-presented-as-a-hungarian-folk-dance/
http://youtu.be/lyZQPjUT5B4
http://www.youtube.com/user/AlgoRythmics?feature=watch

What Sorting Algorithms Sound Like

http://youtu.be/t8g-iYGHpEA
http://youtu.be/kPRA0W1kECg

Bubble Sort

http://en.wikipedia.org/wiki/Bubble_sort

Bucket Sort

http://en.wikipedia.org/wiki/Bucket_sort

Also In The November 2013 Issue

My Adventures with Raspberry Pi

Open source hardware geared towards artists, hobbyists, designers, and students, is a viable and far less expensive alternative to build your own computers.

Beth Rosenberg Talks How Tech Kids Unlimited Helps Kids Who Learn Differently

With a wave of kids with special needs graduating high school, how can technology help them with resumes, college, jobs, and careers?

Stop Words

A clever technique to speed up database searches also is an interesting concept.

More Fun with Raspberry Pi

Here are some videos, and links to even more videos, to learn how to use your Raspberry Pi and have all kinds of fun with Pi projects.

My goal wasn’t to make a ton of money. It was to build good computers.

News Wire Stories for November 2013

Interesting stories about computer science, software programming, and technology for the month of October 2013. More stories can be found at the Software Programming and Computer Science News Wire link at the top of every page of this site.

Bubble Sorts

With a bubble sort, numbers sort themselves as they bubble to the left of a group of numbers. Here's a fun catchy video to explain.

The 7 Bridges of Königsberg

This month's math puzzle dates back to 1735 when it was first solved by Leonhard Euler, a Swiss mathematician and physicist.

Pair Programming

From the start of computing history, people have tried to optimize the software programming process. This includes having two coders work together to code software.

Learn More Links for November 2013

Links from the bottom of all the November 2013 articles, collected in one place for you to print, share, or bookmark.

Icon-itis

The release this fall of Apple's iOS7 operating system is a great opportunity to explore the history of computer interface design.

Functions

Managing inputs and outputs is a key problem programming languages face. Here's how a few languages use functions to manage and transform data.