The Bubble Sort algorithm sorts an array of items in increasing order. It steps through the array and compares the adjacent elements. If they are not sorted, it swaps them. It then keeps repeating the procedure until the array is fully sorted. Let’s jump into an example.

The following elements are compared during the first iteration: 0 and 1, 1 and 2, 2 and 3, 3 and 4, and 4 and 5. In the first comparison of the first iteration, elements at indices 0 and 1 are compared. Since 3 is less than 7, the elements remain in their current positions.

Next, elements at indices 1 and 2 are compared. Since 7 is larger than 1, the elements are swapped.

Next, elements at indices 2 and 3 are compared. Since 7 is larger than 4, the elements are swapped.

Moving to elements 3 and 4, the algorithm compares the values 7 and 6. Since 7 is larger than 6, the values are swapped.

Lastly, elements at indices 4 and 5 are compared. Since 7 is less than 5, the elements are swapped.

This completes the first iteration. We know that the last element is fully sorted. In the next iteration the last element will not be compared. So, in iteration two the following comparisons will occur: 0 and 1, 1 and 2, 2 and 3, and 3 and 4.

The Bubble Sort algorithm begins the second iteration. Values at indices 0 and 1 are compared. Since 3 is greater than 1, the elements are swapped.

Next, the algorithm compares the values 3 and 4. Since 3 is less than 4, the values remain in their current positions.

Values at indices 2 and 3 are compared. Since 4 is less than 6, the values are not swapped.

The Bubble Sort algorithm compares the values at indices 3 and 4. Since 6 is greater than 5, the elements are swapped.

By inspecting the array visually, we can quickly see that the array is sorted, but the Bubble Sort algorithm keeps going since it doesn’t know that it’s finished. It starts the third iteration. Since 1 is less than 3, the values are not swapped.

Finally, values 4 and 5 are compared. Since 4 is less than 5, the values remain in their current positions. This finishes the third iteration. The Bubble Sort algorithm guarantees that it has found the last 3 numbers in the sequence.

Bubble Sort starts the fourth iteration. Since 1 is less than 3, the values are not swapped.

Next, the algorithm compares values at indices 1 and 2. Since 3 is less than 4, the elements remain in their current positions. This ends the fourth iteration. The algorithm guarantees that the last 4 digits have been sorted. One more iteration to go.

The Bubble Sort algorithm starts working on the fifth iteration. It has only one comparison: the comparison between values 1 and 3. Since 1 is less than 3, the values remain in their current positions and the algorithm finishes the fifth iteration.

There are no further comparisons to be performed. The Bubble Sort algorithm has sorted the array in n-1 iterations, which in this case equals 5.

The following example was deliberately chosen to show that even though the Bubble Sort algorithm completed the sort in 2 iterations, n-1 iterations were still needed to finish the execution of the algorithm. It can be deduced that the Bubble Sort algorithm is not efficient for large data sets; it always runs in O(n2).

Bubble Sort Code

Now that we’ve had the opportunity to go through an example, we can begin writing the code. As I stated in the introduction, I will walk you through my entire thought process. So, let’s open up our editor and start writing some code.

Create a new java file and call it Main.java. The class should have your standard public static void main() method. In fact, each of our algorithms will have a main() method; this is so that we can test our algorithm.

public class Main {
    
    public static void main(String[] args) {
        System.out.println("Bubble Sort");
    }
}

I normally run a program like the one above just to make sure that it’s actually functioning. You should get an output in your console that states: Bubble Sort.

Next, let’s make sure that we have the understanding of what the algorithm does. Of course you should reread the article if you’re not familiar with the content enough, but I’ll add the recap here:

The Bubble Sort algorithm sorts an array of items in increasing order. It steps through the array and compares the adjacent elements. If they are not sorted, it swaps them. It then keeps repeating the procedure until the array is fully sorted.

Let’s create the bubbleSort() method first and then read through the description together. In the next article and onwards, we’ll skip a few of these steps, but for now I think it’s important to work through an example fully.

Let’s dissect the bubbleSort() method so far. It’s private since it lives in the same class and is not being called outside of the Main class. It’s static since the main() method is static and we don’t need to instantiate the class in order to call the bubbleSort() method. It’s void since it’s currently not returning anything. As of now, there are no parameters; it simply prints out Bubble Sort. It’s being called from the main() method. Run the program and you’ll see that it prints out Bubble Sort again. Nothing crazy so far.

public class Main {
    
    public static void main(String[] args) {
        bubbleSort();
    }
  
    private static void bubbleSort() {
        System.out.println("Bubble Sort");
    }
}

Reading through our description of the Bubble Sort algorithm, it states that this “algorithm sorts an array of items.” When I see this, I know that my bubbleSort() method will need to accept an array of items to sort. Let’s create an array called sort inside of the main() method and let’s declare the sort parameter in the bubbleSort() method. We’ll pass the sort array to the bubbleSort() method and print out the first element.

public class Main {
    
    public static void main(String[] args) {
        int[] sort = {78,39,14,56,88,94,108,5,15};
      
        bubbleSort(sort);
    }
  
    private static void bubbleSort(int[] sort) {
        System.out.println(sort[0]);
    }
}

If you run the program, you’ll see the following output: 78. It feels like something is happening already, doesn’t it? The next portion of our definition states that the bubbleSort() algorithm “steps through the array and compares the adjacent elements.” Although there are numerous ways to do this, what I’m hearing is that there is a loop of some sort that goes through the array and swaps the values until they’re sorted. This is usually where most people start to panic the first time. But, let’s go through this one step at a time.

public class Main {
    
    public static void main(String[] args) {
        int[] sort = {78,39,14,56,88,94,108,5,15};
      
        bubbleSort(sort);
    }
  
    private static void bubbleSort(int[] sort) {
      
        for ( int i = 0; i < sort.length - 1; i++ ) {
            if ( sort[i] > sort[i + 1] ) {
                System.out.println("Swap " + sort[i] + " with " + sort[i + 1]);
            }
        }
    }
}

We’ll sort through the array. If the value at the current index is larger than the value located at index + 1, swap the two values.

Seems simple enough. Since I know that we’re looking at values at specific indices, I’ll use a for loop since I can initialize an int value and loop through it until I reach the end.

Reviewing the code, we can see that we now have a for loop that starts at i = 0 and ends at the final value of the array, which is achieved by getting the length of the sort array and subtracting 1 from it (since the array index value starts at 0). Within the loop, we compare the current element value with the element value right after. If the current element is larger than the element after it, we print out that we want to swap the values. Run the code and you’ll see that the first value is always larger than the next value.

However, we haven’t done any sort of swapping yet. We need to actually swap the values now if the statement holds true. Which means that we have to set sort[i] = sort[i + 1] and vice-versa. The only problem with that is that you’ll be overriding the value instantly. Walk through it and you can see that if we set sort[i] to equal 39, it overrides it’s current value of 78. Then, when we go to set sort[i + 1] to equal the value of sort[i], it will also be 39; the 78 is gone. So, we need to temporarily store the value of sort[i] somewhere else while we do the swap. We’ll introduce a temp variable to store it there.

public class Main {
    
    public static void main(String[] args) {
        int[] sort = {78,39,14,56,88,94,108,5,15};
      
        bubbleSort(sort);
    }
  
    private static void bubbleSort(int[] sort) {
      
        int temp;
      
        for ( int i = 0; i < sort.length - 1; i++ ) {
            if ( sort[i] > sort[i + 1] ) {
                temp        = sort[i];
                sort[i]     = sort[i + 1];
                sort[i + 1] = temp;
            }
        }
    }
}

Did it work? Let’s print out the content and see what we get. To print out an array, we’ll utilize the Arrays library. Simply modify your main method to utilize the Arrays library and print out the contents of the bubbleSort() method call. Don’t forget to import the Arrays library up top.

mport java.util.Arrays;

public class Main {
    
    public static void main(String[] args) {
        int[] sort = {78,39,14,56,88,94,108,5,15};
      
        bubbleSort(sort);
      
        System.out.println( Arrays.toString(sort) );
    }
  
    private static void bubbleSort(int[] sort) {
      
        int temp;
      
        for ( int i = 0; i < sort.length - 1; i++ ) {
            if ( sort[i] > sort[i + 1] ) {
                temp        = sort[i];
                sort[i]     = sort[i + 1];
                sort[i + 1] = temp;
            }
        }
    }
}

Before we run the code, let’s take a look at logic behind what was written. The Arrays.toString() method accepts the sort array and the entire result is passed to the System.out.println() method, which prints out the content of the sort array. Shouldn’t we pass bubbleSort(sort) as an argument to the Arrays.toString() method? Also, the bubbleSort() method doesn’t actually return anything, hence the void declaration, so how will there be any results? Arrays are special since you’re passing the reference to the array when you’re calling the bubbleSort() algorithm. The bubbleSort() method then modifies the array directly and doesn’t actually create a copy of it like it would with other data types like int’s. If you’re interested if finding out more, you can read about pass-by-reference vs pass-by-value on your own. We’ll be moving on with the algorithm. I know you’re eager to see the result.

[39, 14, 56, 78, 88, 94, 5, 15, 108]

Did you get the same thing? Something seems a little off. It looks like the only value that’s sorted is 108. What happened to the rest of the values? Well, believe it or not, we didn’t really sort them. If you walk through the algorithm that we outlined in the beginning of this chapter, you’ll see that this is actually what the expected outcome is. We only did the first pass on the array. After the first pass, the last value is sorted. We then have to repeat the process again to sort the remainder of the values. The second pass will sort the second to the last value. The third pass will sort the third to the last and so on.

How do we do this? Well, we call the bubbleSort() method for the second time. The easiest way to test our hypothesis is to actually call the bubbleSort() algorithm again. So, let’s do it.

If we run the program, the expected outcome will be that 94 moves to the second to the last value since it’s the next largest value. If we run the program and look at the outcome, we can see that the result is in fact as expected.

import java.util.Arrays;

public class Main {
    
    public static void main(String[] args) {
        int[] sort = {78,39,14,56,88,94,108,5,15};
      
        bubbleSort(sort);
        bubbleSort(sort);
      
        System.out.println( Arrays.toString(sort) );
    }
    
    //...
}

[14, 39, 56, 78, 88, 5, 15, 94, 108]

Let’s do it once more. The next expected result is that the value 88 moves to the 3rd to the last space.

And sure enough, it does: [14, 39, 56, 78, 5, 15, 88, 94, 108].

We are making a couple of mistakes here though. First, we’re only calling a single pass of the algorithm each time. The algorithm should provide us with a final answer. The second mistake that we’re making is that each time we call the bubbleSort() method, the algorithm runs through the entire array. Even though the last elements are sorted, they’re compared again. We need to eliminate that. Let’s brainstorm together.

In order to sort the entire array, we would need to call the bubbleSort() method n-1 times, where n represents the number of elements in the array. Why n-1 and not n times? Because you’re comparing two values. When you’re on your (n-1)th time, you’re actually comparing two values. No reason to compare the two values again. Go ahead, give it a shot. Repeat the bubbleSort() method 8 times, and then 9. You’ll see that you get the same result.

import java.util.Arrays;

public class Main {
    
    public static void main(String[] args) {
        int[] sort = {78,39,14,56,88,94,108,5,15};
      
        bubbleSort(sort);
        bubbleSort(sort);
        bubbleSort(sort);
        bubbleSort(sort);
        bubbleSort(sort);
        bubbleSort(sort);
        bubbleSort(sort);
        bubbleSort(sort);
      
        System.out.println( Arrays.toString(sort) );
    }
    
    //...
}

Your array should be sorted: [5, 14, 15, 39, 56, 78, 88, 94, 108]. When I look at the above code, I see that I keep calling the same method over and over again, and something inside of me thinks: recursive method. A recursive method is a method that calls itself. How does it do this? By literally calling itself from inside of its method body. Let’s see if we can reduce the number of method calls. First, let’s remove the 8 bubbleSort() calls from inside of the main() method and replace it with one method call.

import java.util.Arrays;

public class Main {
    
    public static void main(String[] args) {
        int[] sort = {78,39,14,56,88,94,108,5,15};
      
        bubbleSort(sort);
      
        System.out.println( Arrays.toString(sort) );
    }
    
    //...
}

Next, let’s call the bubbleSort() method from inside of the bubbleSort() method.

import java.util.Arrays;

public class Main {
    
    public static void main(String[] args) {
        int[] sort = {78,39,14,56,88,94,108,5,15};
      
        bubbleSort(sort);
      
        System.out.println( Arrays.toString(sort) );
    }
  
    private static void bubbleSort(int[] sort) {
      
        int temp;
      
        for ( int i = 0; i < sort.length - 1; i++ ) {
            if ( sort[i] > sort[i + 1] ) {
                temp        = sort[i];
                sort[i]     = sort[i + 1];
                sort[i + 1] = temp;
            }
        }
      
        bubbleSort(sort);
    }
}

My IDE is smart enough to know that we just created an infinite loop. Whereas before we called the bubbleSort() method 8 times, this time we’re calling it an infinite amount of times. Why did we put it outside of the for loop? Because the for loop goes through a single pass. Only after the pass is complete do we call the bubbleSort() method again. You can attempt to run this code now, but it’ll just error out after a while. Instead, we have to figure out a way to break out of the loop.

Back to brainstorming. We know that one flaw that we had with our 8 call design is that it looped through the entire array each time. Since we know that each time the array runs, the last value is sorted, we can remove the last value from the for loop and only loop through the array elements that are not sorted. That means that we have to pass the length of the array to the bubbleSort() algorithm and decrement its traversable length each time.

We’ll have to make a few modifications to our code. First, we’ll have to pass the newly modified length value along with our sort array to the bubbleSort() method. We can do this by declaring the int length parameter: bubbleSort(int[] sort, int length). Next, we’ll need to make sure that the length argument is used in our for loop, instead of our derived sort.length value. Finally, we pass the n – 1 length value to the bubbleSort() method recursively. We can do this by passing length-1: bubbleSort(sort, length-1).

There is one additional place where we’ll need to modify the bubbleSort() method call and that’s inside of our main method. We’ll start off by passing the current length of the array.

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[] sort = {78,39,14,56,88,94,108,5,15};
        int length = sort.length;

        bubbleSort(sort, length);

        System.out.println( Arrays.toString(sort) );
    }

    private static void bubbleSort(int[] sort, int length) {

        int temp;
      
        for ( int i = 0; i < length - 1; i++ ) {
            if ( sort[i] > sort[i + 1] ) {
                temp        = sort[i];
                sort[i]     = sort[i + 1];
                sort[i + 1] = temp;
            }
        }

        bubbleSort(sort, length - 1);
    }
}

However, the editor still doesn’t seem to like it. If you try to run the program, you’ll see that it throws the same type of error. But why? Well, because we keep subtracting length to infinity. We need to stop at some point. But where? If you think about it, on the last pass, the Bubble Sort algorithm compares the first two values. The indices of those first two values are 0 and 1, which means that we need to stop the traversal when length equals 1.

We can implement that by checking whether the value of the length argument is 1 whenever the bubbleSort() algorithm is first called. If it is, we just want to terminate it by executing a return statement.

public class Main {

    public static void main(String[] args) {
        int[] sort = {78,39,14,56,88,94,108,5,15};
        int length = sort.length;

        bubbleSort(sort, length);

        System.out.println( Arrays.toString(sort) );
    }

    private static void bubbleSort(int[] sort, int length) {
      
        if (length == 1) {
            return;
        }

        int temp;
      
        for ( int i = 0; i < length - 1; i++ ) {
            if ( sort[i] > sort[i + 1] ) {
                temp        = sort[i];
                sort[i]     = sort[i + 1];
                sort[i + 1] = temp;
            }
        }

        bubbleSort(sort, length - 1);
    }
}

Time for the moment of truth. Run the program and see if it gives you the results that you want. If you did everything up to this point, your array should be fully sorted:

[5, 14, 15, 39, 56, 78, 88, 94, 108]

There is one final adjustment to do. What happens if you pass an empty array to the bubbleSort() algorithm? That’s right, error.

So how do you combat this? Simple enough. We need to make sure that our check accounts for that. We’ll just make sure that the bubbleSort() method terminates if the length of the array is less than or equal to 1 instead of only equal to 1. And with that small modification, our bubbleSort() algorithm is complete.