1. Introduction
In this quick article, we’ll explore the Bubble Sort algorithm in detail, focusing on a Java implementation.
This is one of the most straightforward sorting algorithms; the core idea is to keep swapping adjacent elements of an array if they are in an incorrect order until the collection is sorted.
Small items “bubble” to the top of the list as we iterate the data structure. Hence, the technique is known as bubble sort.
As sorting is performed by swapping, we can say it performs in-place sorting.
Also, if two elements have same values, resulting data will have their order preserved – which makes it a stable sort.
2. Methodology
As mentioned earlier, to sort an array, we iterate through it while comparing adjacent elements, and swapping them if necessary. For an array of size n, we perform n-1 such iterations.
Let’s take up an example to understand the methodology. We’d like to sort the array in the ascending order:
4 2 1 6 3 5
We start the first iteration by comparing 4 and 2; they are definitely not in the proper order. Swapping would result in:
[2 4] 1 6 3 5
Now, repeating the same for 4 and 1:
2 [1 4] 6 3 5
We keep doing it until the end:
2 1 [4 6] 3 5
2 1 4 [3 6] 5
2 1 4 3 [5 6]
As we can see, at the end of the first iteration, we got the last element at its rightful place. Now, all we need to do is repeat the same procedure in further iterations. Except, we exclude the elements which are already sorted.
In the second iteration, we’ll iterate through entire array except for the last element. Similarly, for 3rd iteration, we omit last 2 elements. In general, for k-th iteration, we iterate till index n-k (excluded). At the end of n-1 iterations, we’ll get the sorted array.
Now that in you understand the technique, let’s dive into the implementation.
3. Implementation
Let’s implement the sorting for the example array we discussed using the Java 8 approach:
void bubbleSort(Integer[] arr) {
int n = arr.length;
IntStream.range(0, n - 1)
.flatMap(i -> IntStream.range(1, n - i))
.forEach(j -> {
if (arr[j - 1] > arr[j]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
});
}
And a quick JUnit test for the algorithm:
@Test
void whenSortedWithBubbleSort_thenGetSortedArray() {
Integer[] array = { 2, 1, 4, 6, 3, 5 };
Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 };
BubbleSort bubbleSort = new BubbleSort();
bubbleSort.bubbleSort(array);
assertArrayEquals(array, sortedArray);
}
4. Complexity and Optimization
As we can see, for the average and the worst case, the time complexity is O(n^2).
In addition, the space complexity, even in the worst scenario, is O(1) as Bubble sort algorithm doesn’t require any extra memory and the sorting takes place in the original array.
By analyzing the solution carefully, we can see that if no swaps are found in an iteration, we don’t need to iterate further.
In case of the example discussed earlier, after the 2nd iteration, we get:
1 2 3 4 5 6
In the third iteration, we don’t need to swap any pair of adjacent elements. So we can skip all remaining iterations.
In case of a sorted array, swapping won’t be needed in the first iteration itself – which means we can stop the execution. This is the best case scenario and the time complexity of the algorithm is O(n).
Now, let’s implement the optimized solution.
public void optimizedBubbleSort(Integer[] arr) {
int i = 0, n = arr.length;
boolean swapNeeded = true;
while (i < n - 1 && swapNeeded) {
swapNeeded = false;
for (int j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
swapNeeded = true;
}
}
if(!swapNeeded) {
break;
}
i++;
}
}
Let’s check the output for the optimized algorithm:
@Test
void givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray() {
Integer[] array = { 2, 1, 4, 6, 3, 5 };
Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 };
BubbleSort bubbleSort = new BubbleSort();
bubbleSort.optimizedBubbleSort(array);
assertArrayEquals(array, sortedArray);
}
5. Conclusion
In this tutorial, we saw how Bubble Sort works, and it’s implementation in Java. We also saw how it can be optimized. To summarize, it’s an in-place stable algorithm, with time complexity:
- Worst and Average case: O(n*n), when the array is in reverse order
- Best case: O(n), when the array is already sorted
The algorithm is popular in computer graphics, due to its capability to detect some small errors in sorting. For example, in an almost sorted array, only two elements need to be swapped, to get a completely sorted array. Bubble Sort can fix such errors (ie. sort this array) in linear time.
As always, the code for the implementation of this algorithm can be found over on GitHub.