How to Write a Java Bubble Sort
When programmers talk about bubble sorts, they are not talking about the water bubbles that you’ve probably blown at some point in your life. They are talking about a sorting algorithm that is used to order a list of items.
In this guide, we’re going to talk about bubble sorts and how they work. We’ll go on to implement a bubble sort using Java so that you can understand how this algorithm translates to code. Without further ado, let’s dive into Java bubble sorts!
What is a Java Bubble Sort?
A bubble sort is an algorithm that sorts values by comparing adjacent elements and swapping them if they appear in the wrong order.
This process repeats until every item in a list is ordered correctly. Bubble sorts can be used to sort a list either in ascending or descending order.
Bubble sorts are the first sort taught in algorithms classes. This is because they are easier to understand than other sorts, like an insertion sort or a selection sort, and provide a good introduction to sorting algorithms.
Bubble sorts are most effective when the data is already almost sorted. However, if your data is not sorted at all, another type of sort may be more efficient.
How do Bubble Sorts Work?
Before we start writing the code for a Java bubble sort, we have to first understand how this algorithm is implemented in practice.
Consider the following list:
5 | 9 | 2 | 7 |
Our bubble sort starts by comparing the first and second elements in our list.
If the first element is greater than the second element, these elements swap positions. In this case, 5 is not greater than 9, so the elements stay in their same places.
Then, our sort will compare the next two items in our list. 9 is greater than 2, and so these two numbers swap:
5 | 2 | 9 | 7 |
This process repeats until every item in the list has been compared. In this case, there is one more comparison to perform: is 9 greater than 7? 9 is greater than 7, so these numbers swap:
5 | 2 | 7 | 9 |
Our list is almost ordered. Once every item has been compared, the bubble sort will start over again until every element is sorted.
5 is greater than 2, and so these numbers swap.
2 | 5 | 7 | 9 |
Our list is now ordered correctly. Our bubble sort will keep comparing numbers until it gets to the end of the list, and then it will stop. That’s all there is to a bubble sort. It’s definitely an easy algorithm to use once you get the hang of it.
How to Write a Java Bubble Sort
Knowing the theory is one thing but you came here to learn about Java bubble sorts. We’d best discuss how to implement a bubble sort in Java.
There are two types of bubble sorts:
- Standard bubble sort
- Optimized bubble sort
The standard bubble sort makes all possible comparisons even if an array is sorted. This increases the time it takes for the bubble sort to execute. This makes the sort less efficient.
Optimized bubble sorts keep track of whether a list is sorted by using an additional variable. This allows us to stop our sort as soon as our list has been sorted.
Let’s start by writing a standard bubble sort.
Standard Bubble Sort
To start, we’re going to import the Arrays library into our code. We’ll use this later in our code to print out our list of sorted numbers to the console:
import java.util.Arrays;
Now that is out of the way, we can begin writing our algorithm.
We’ll start by defining a class called BubbleSort which stores the code for our Java program, and a function which performs our sort:
"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"
Venus, Software Engineer at Rockbot
class BubbleSort { void sortNumbers(int array[]) { int size = array.length; for (int item = 0; item < size - 1; item++) { for (int j = 0; j < size - item - 1; j++) { if (array[j] > array[j + 1]) { int temporary = array[j]; array[j] = array[j + 1]; array[j + 1] = temporary; } } } } }
We have declared a function called sortNumbers
which accepts a variable as a parameter. This function starts by calculating the size of the list of numbers we specify.
Once this has been calculated, a for loop is initialized. This loop walks through every item in our array. We initialize another for loop which allows us to compare each item in the array.
If the item on the left of a list is greater than the number on the right, the values are swapped. Otherwise, nothing happens.
We perform this swap by assigning the value on the left to a variable called “temporary”. We assign the value on the right the value that was on the left side of the comparison. Then, the value on the left is assigned the value of the temporary variable.
If 6 and 5 were being compared, they would be swapped. So, our list would appear as: 6, 5.
Our program doesn’t do anything just yet. We haven’t written a main program that calls our function and gives it a list to sort.
Add the following code below the sortNumbers
function in your code:
public static void main(String args[]) { int[] toSort = { 5, 9, 2, 7 }; BubbleSort sortingAlgorithm = new BubbleSort(); sortingAlgorithm.sortNumbers(toSort); System.out.println(Arrays.toString(toSort)); }
We have declared a variable called toSort which stores the list of values we want to sort. We’ve then declared an instance of the BubbleSort class called sortingAlgorithm, which we use on the next line of code to call the sortNumbers
function. When this function is called, our list is sorted.
Finally, we use the Arrays.toString()
method to convert our list to a string so that we can print it out to the console. Our code returns:
[2, 5, 7, 9]
We now have a sorted array!
Optimized Bubble Sort
There is a way to make our code more efficient. Right now, our sort continues until it has made all possible comparisons. This means that even if our array is sorted, the sort will keep going until those comparisons are complete.
We can prevent this behavior by adding a new variable to our code. This will allow us to stop our sort if the list is swapped. Let’s add this variable to our sortNumbers
function from earlier:
class BubbleSort { void sortNumbers(int array[]) { int size = array.length; for (int item = 0; item < size - 1; item++) { boolean hasSwapped = false; for (int j = 0; j < size - item - 1; j++) { if (array[j] > array[j + 1]) { int temporary = array[j]; array[j] = array[j + 1]; array[j + 1] = temporary; hasSwapped = true; } } if (hasSwapped == false) { break; } } } }
We’ve made three changes to our code. Inside our first for loop we have declared a variable called “hasSwapped”. This variable keeps track of whether a swap has been made. By default, this variable is set to “false”. If a swap is made, the value of this variable is set to “true”.
At the end of our for loop, we have added an if statement to check if hasSwapped is equal to false. If no swaps have been made, the array is sorted. We use the “break” keyword to stop our loop from executing if hasSwapped is equal to false.
Let’s run our code using the main program we wrote earlier and see what happens:
[2, 5, 7, 9]
Our list has been sorted, but this time our algorithm is more efficient. If we used a larger list with more values to sort, the superior performance of this algorithm would be clearer. That’s it, you have written an optimized bubble sort in Java!
Conclusion
Bubble sorts are used to sort lists in ascending or descending order. They work by comparing adjacent values and swapping them if they are in the wrong order.
There are two types of bubble sort: standard and optimized. Standard bubble sorts perform a predefined number of swaps whereas optimized bubble sorts only keep sorting until a list is sorted.
Now you’re ready to start writing bubble sorts in Java like an expert!
About us: Career Karma is a platform designed to help job seekers find, research, and connect with job training programs to advance their careers. Learn about the CK publication.