Learn Bubble Sort with Playing Cards

Let’s say you have an unordered list of numbers and you wanted to put them in order from lowest to highest value. How would you do that? You’re probably thinking that you would just look at all the numbers, find the lowest number and put it at the beginning of your list. Then you would find the next largest number and put it in the second spot in the list, and so on until you’ve ordered the entire list of numbers. It’s simple, basic, and not very exciting. Now, let’s say that instead of ordering the list yourself, you decide it’s a better idea to write a computer program to order the list for you. Now you don’t have to deal with moving the numbers around, you just need to tell your program how to move the numbers, and then let the program handle any list you give it.

So how do you write your program to order the list? One of the most basic techniques for putting lists in order is the Bubble Sort algorithm. To understand how a Bubble Sort works, let’s use it on a few random playing cards to get them in order. after we walk through the algorithm with cards, we’ll take a look at a Bubble Sort implemented in code.

Let’s Sort Some Playing Cards

The image below shows we have five cards (with unknown values) that we need to put in order using a Bubble Sort.

The first step in a Bubble Sort is to compare the first two values with each other. Here we see the first two values are an Ace (1) and a Queen (12). They are in order, so we move on to the next card.

Now we compare the Queen with nine.

Since the Queen is a larger value, it trades places with the nine, as seen below.

Now we move on to the next card value. Since the Queen is a larger value than the two, they trade places.

Now, we move on to the last card in the list. The Ace is less than the Queen, so once again the cards trade places.

At this point, each card in this list has been compared to a neighboring card at least once. The result is that the largest value among these five cards has “bubbled” to the end of the list. But, we’re not done yet. After only one pass through we can only be sure that the last card is in the correct position. So let’s run the the cards again.

Starting at the beginning with the first two cards, Ace is compared with 9. Since Ace is less than nine, there is no change in position.

The next card, the two of hearts, is less than nine. So they trade places.

Next, nine is compared with an Ace. Since nine is greater than the Ace, they switch positions.

With this second pass, we can now be sure that the final two cards are correct. You should be starting to see a pattern here. We continue the process until all the cards are in order.

Implement Bubble Sort in JavaScript

Now that we understand the Bubble Sort process from the playing card demonstration, let’s implement it. Let’s use JavaScript for a simple example.

The script begins by creating an array that holds 5 values, and assigning random numbers to the array. Once the array is created and populated, we print the array and values to the console.

var sortMe = new Array();
var arrayLength = 5;
var i = 0;
for(; i < arrayLength; i++) {
    sortMe[i] = Math.floor((Math.random()*20)+1);
}

var logText = "";
i = 0;
for(; i < arrayLength; i++) {
    logText += sortMe[i] + ", ";
}
console.log("Starting Values: \t" + logText);

Now we need to sort the array. The sort is done by using two loops and an if statement.

i = 0;
var didSwap = true;
var temp;
for(; i < arrayLength && didSwap; i++) {
    didSwap = false;
    var j = 0;
    for(; j < (arrayLength - 1); j++) {
        if(sortMe[j] > sortMe[j+1]) {
            temp = sortMe[j];
            sortMe[j] = sortMe[j+1];
            sortMe[j+1] = temp;
            didSwap = true;
        }    
    }

    logText = "New Order:\t\t";
    k=0;
    for(; k < arrayLength; k++) {
        logText += sortMe[k] + ", ";
    }
    console.log(logText);
}

When this script is executed, it will log to the console the original unmodified array, then it will print the modified array after each pass. Here are the log messages I got when I ran this code:

Starting Values: 	7, 9, 2, 16, 4,
New Order:		7, 2, 9, 4, 16,
New Order:		2, 7, 4, 9, 16,
New Order:		2, 4, 7, 9, 16,
New Order:		2, 4, 7, 9, 16, 

Notice that the first pass through the starting values put 16 at the end of the list (just like the playing cards example). Then each pass after that “bubbled” the next highest number up. Here is the complete example.

Problems with Bubble Sort

Great. We now have a way to get our computer program to put lists of numbers in order for us. It’s automatic and it works. However, there are problems with Bubble Sort. That problem is that when confronted with a worst case scenario (long, long lists with lots of numbers that need to be moved) it is slow! More numbers in the list and more numbers that need to be moved increase the complexity of the Bubble Sort. The more complex it gets, the slower it gets. Now, this is true for any sorting algorithm. The problem with the Bubble Sort is that it gets very complex very quickly.

To describe the worst case complexity for an algorithm, computer science generally uses something called Big Oh Notation. The notation for the worst case Bubble Sort is O(n2). I’m not going to go into Big Oh Notation in detail here. If you’re interested in learning more about it, this StackOverflow.com answer does a great job of explaing it in plain language. For the purposes if this article, it’s good to understand that Bubble Sort gets complex (and therefore slow) very quickly. There are other algorithms that do a better job of sorting numbers, but the Bubble Sort is one that is often taught to computer science students first.