Bubble Sorts – 30 STEM Links a Week

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

What Are Bubble Sorts

What Other Sorting Methods are Used in Programming?

What is the Value of Sorting?

Learn More

Bubble Sort as a Hungarian Folk Dance

What Sorting Algorithms Sound Like

Bubble Sort

Bucket Sort