Bubble Sort in Java is an introductory and classic algorithm in computer science. It is used to sort the unsorted collection. Items could be of number, string, or any other types. This algorithm iterates through a collection and works by repeatedly swapping the adjacent elements in the collection when the adjacent elements are not in order. And this algorithm continues to swap unsorted elements until the whole collection is sorted. Ordering or sorting could be ascending or descending. If you think the definition is little bit confusing, wait and go through the rest of the article. It is really very easy and simple. After explaining the working steps, you will be more clear about this Bubble Sort in Java.
For explaining the working steps, let’s consider an unsorted collection of items:
[32, 30, 55, -10, 50, 5]
This is an unsorted collection or list of integer numbers. Our target is to sort the entire list in ascending order. First, we consider the whole list is unsorted. So the largest number will be bubbled up (swapped) to the end of the list. Therefore, we can say the last number is out of order. So the last unsorted item’s position is 5.
First Iteration
According to the definition of the Bubble Sort in Java Algorithm, we compare the first 2 adjacent elements, here the first 2 adjacent elements are 32 and 30 respectively. After comparing, here 32 is greater than 30. Consequently, these two items will be swapped. Now the collection looks like [30, 32, 55, -10, 50, 5]. Then the comparison will be repeated on 32 and 55. In this case, 55 is greater than 32. So we don’t need to swap these adjacent elements. If we repeat this comparison and swapping until the last unsorted item, the list will look like this:
[30, 32, -10, 50, 5, 55]
Second Iteration
Now, for this iteration, our last unsorted item’s position is 4. Because, after the first iteration, according to the Bubble Sort in Java Algorithm, we are confirmed that, the last item is sorted. So for the case of the second iteration, it will be continuing until the 4th position of the collection (last unsorted item). For this iteration, the first 2 adjacent elements (30, 32) will not exchange their position. The second 2 adjacent elements (32 and -10) will exchange or swap their position. Now the third 2 adjacent elements are 32 and 50, and they will be swapped. By following this way, after completing the iteration, the list will be looked like this:
[30, -10, 32, 5, 50, 55]
If we complete all the iterations, all items of the collection will be sorted.
This is the sorted item got after implementing the Bubble Sort in Java Algorithm:
[-10, 5, 30, 32, 50, 55]
In this algorithm, for each iteration, the largest item of taken adjacent elements bubbled up to the last unsorted position. The smallest number would be bubble up to the first unsorted item of the list if we could consider it as descending order sorting. On the other hand, it also could be possible to implement this algorithm in reverse way, so that the smallest item will bubble up. And this is the concept that gives its name Bubble Sort Algorithm.
An Example of Bubble Sort in Java Algorithm
After executing the for loop of the main method, if we print the arrayList, our printed list will be this: “[-10, 5, 30, 32, 50, 55]“.
Here, in the first for loop, we consider the last item of the collection is unsorted. After each iteration, the last unsorted item’s position is decreased by 1 as we are getting last item sorted on each iteration. And in the second for loop, we check each adjacent element whether they need to bubble up (swap) or not. If it is, we call the swap method for bubbling up.
For visualizing and illustrating the scenario of the Bubble Sort in Java Algorithm, here is an animation.
Optimized Solution
On the above solution, all the iterations will be executed whether they are already sorted or not. But what if we can make our program to ignore the sorted part? Let’s have an example:
What will happen if we use the list below instead of the above list (used as input of the first example program)?
[46, 34, 40, 35, 44, 48]
If we follow the exact Bubble Sort in Java Algorithm procedure for the new list in the same way we described in the working steps section we will get a sorted list, looks like this: [34, 35, 40, 44, 46, 48]. But if we observe each iteration, we can see that after the second iteration we are getting our expected output (ordered list). But according to the Bubble Sort Algorithm, we are tended to go for further all iterations which is not required practically and we can make our program more efficient by ignoring further iterations after getting the ordered list.
For getting this efficient solution, lets have a look on the example below:
In the program above with the mentioned input, we will get the ordered list after just the second iteration and when the outer loop executes the third iteration, the “if” condition of the inner loop will not be fully filled. Consequently, the boolean value “bubbledUp” will remain the same (false) as initialised and it will indicate that no adjacent elements bubbled up (swapped). It means, all items have been sorted out in the previous iteration. Finally, based on the “bubbledUp” value the program will get out from the outer loop. It is a more efficient way to implement the Bubble Sort Algorithm than the previous one. But complexity is the same as Big-O notation always defines the worse case of an algorithm.
Complexity of the Bubble Sort Algorithm
As Bubble Sort in Java Algorithm uses two loops, it is very clear that the time complexity of this algorithm is quadratic or O(n2) in Big-O notation. On the other hand, for the case of optimised solution, it is also quadratic or O(n2). Because Big-O notation always considers the worse case. The optimised solution will get benefit if the input is very wise to sort. It might be a best-case scenario.
Finally, we already realised that this algorithm is a very easy understanding algorithm. But it is pretty slow as it takes long time for a lot of comparisons. You can use this algorithm if you deal with a very small set of data or if you don’t need to think about the time an algorithm takes to run. But most of the time you will avoid it if you compare this algorithm with some other efficient algorithms.
