Sort An Integer Array Using Bubble Sort With Java

Previously you saw an implementation of Quicksort, one of the better sorting algorithms. This time we’re going to look at a much inferior sorting algorithm which generally makes its appearance in introduction to computer science type courses. I’m talking about the Bubble Sort algorithm.

Bubble Sort via Wikipedia:

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.

The Bubble Sort algorithm is sub-par because of the outrageous time-complexity that it has for all sorting calls and we’re going to see why.

public class Sorting {

    public void bubbleSort(int[] unsorted) {

        for(int i = 0; i < unsorted.length; i++) {
            for(int j = 0; j < unsorted.length; j++) {
                if(unsorted[i] < unsorted[j]) {
                    int temp = unsorted[i];
                    unsorted[i] = unsorted[j];
                    unsorted[j] = temp;
                }
            }
        }

    }

}

In the above code notice that our Bubble Sort implementation has two nested loops all iterating through the length of the array. For every array, sorted or not, the outer loop will iterate n times and the inner loop will iterate n times. This means that in every scenario our time-complexity will be O(n^2) which is terrible.

This implementation can be improved slightly to handle the scenario where the array is already sorted:

public class Sorting {

    public void bubbleSort(int[] unsorted) {
        boolean swapped = true;
        while(swapped) {
            swapped = false;
            for(int i = 0; i < unsorted.length - 1; i++) {
                if(unsorted[i] > unsorted[i + 1]) {
                    int temp = unsorted[i];
                    unsorted[i] = unsorted[i + 1];
                    unsorted[i + 1] = temp;
                    swapped = true;
                }
            }
        }

    }

}

Notice in the above code I’ve stripped out one of the for-loops replacing it with a while loop. This gives us slightly more control in the Bubble Sort algorithm. After entering the while loop we immediately assume the array is sorted so when the for-loop depletes, the algorithm stops, leaving us with a time-complexity of O(n). If it was determined that the array was not sorted in the for-loop, then the full sort happens giving us a time-complexity of O(n^2).

In case you’re interested in testing the above code, you can create a driver class like follows:

public class MainDriver {

    public static void main(String[] args) {

        Sorting s = new Sorting();
        int[] arr = new int[] {5, 3, 8, 9, 2, 1, 7, 10};
        s.bubbleSort1(arr);
        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

    }

}

Then running the following from your Command Prompt or Terminal:

javac MainDriver.java
java MainDriver

Not much to it.

Conclusion

Although very simple to implement, the classic Bubble Sort algorithm is something that you probably should stay away from. If you’re interviewing for a software engineering type position, you may be asked to sort an array. It is in your best interest to choose Quicksort or another algorithm that offers a better time. It is also a good idea to know why exactly one is better than the other.

If you’ve ever been asked a question like this on an exam or in an interview, please share your experience in the comments.

Nic Raboy

Nic Raboy is an advocate of modern web and mobile development technologies. He has experience in C#, JavaScript, Golang and a variety of frameworks such as Angular, NativeScript, and Unity. Nic writes about his development experiences related to making web and mobile development easier to understand.