Bubble Sort Algorithm in Java | Visualization and Examples

In this tutorial, we will learn what the bubble sort algorithm is, how it works, its space and time complexities, its optimized version, and bubble sort implementation in Java.

What is Bubble Sort Algorithm?

Bubble sort is a sorting algorithm that works by comparing the adjacent elements and swapping them based on ascending or descending sorting criteria until the array is in the expected order.

How Does Bubble Sort Work?

I will explain the bubble sort algorithm in ascending order. Let’s assume that we have an unsorted array as follows: [18, 32, -11, 6, 68, 2, -34]

Our aim is to sort these numbers in ascending order. We iterate the array from left to right and do sorting for the last index which is called as indexToBeSorted.

We iterate the unsorted array one by one starting from index 0 to indexToBeSorted and in each iteration, we compare the {value of the current index} with {value of index+1}. If the (value of the current index) is bigger than {value of index+1}, then we will swap these values. We do this until we reach the indexToBeSorted. In this way, we sort the values for indexToBeSorted and the biggest number moved to the indexToBeSorted.

After the first sort iteration for indexToBeSorted, we decrease the indexTobeSorted by 1 (indexToBeSorted – 1) and do the same operations while the indexToBeSorted value is bigger than zero. In this way, we can sort the unsorted array in ascending order with bubble sort.

Let’s visualize the bubble sort algorithm with colorful diagrams.

Bubble Sort Visualization

Our unsorted array of numbers is as follows: And our first indexToBeSorted will be index 6.

Then index 5

Then index 4

Then index 3

Then index 2

Then index 1

and finally, all indexes will be sorted.

And for each iteration for the indexToBeSorted:

• We iterate from index 0 to indexToBeSorted.
• We compare (value of the current index) with (value of the current+1 index).
• If (value of the current index) is bigger than (value of the current+1 index), we swap these values.

Now let’s see how the bubble sort algorithm works visually.

First Iteration

At the 1st iteration, the index to be sorted is 6.

• “Index to be Sorted” is purple.
• (Current Index) colored by red.
• (Current + 1 Index) colored by yellow.
• Cross icon means No Swapping and Double bi-directional arrow icon means Swapping.  Second Iteration

At the 2nd iteration, the index to be sorted is 5 which was colored by purple at the beginning, and at the end, it was sorted, and it was colored as green. Third Iteration

At the 3rd iteration, the index to be sorted is 4 which was colored by purple at the beginning, and at the end, it was sorted, and it was colored as green. Fourth Iteration

At the 4th iteration, the index to be sorted is 3 which was colored by purple at the beginning, and at the end, it was sorted, and it was colored as green. Fifth Iteration

At the 5th iteration, the index to be sorted is 2 which was colored by purple at the beginning, and at the end, it was sorted, and it was colored as green. Sixth Iteration

At the 6th iteration, the index to be sorted is 1 which was colored by purple at the beginning, and at the end, it was sorted, and it was colored as green. It is the last iteration that’s why the index 0 is also sorted as well. Bubble Sort Animation

Bubble Sort in Java

I will share with you two different bubble sort implementations in Java. One of them is for ascending order and the other one is for descending order.

Bubble Sort Java Implementation in Ascending Order

public class BubbleSort {
public static void main(String[] args) {
int[] array = { 18, 32, -11, 6, 68, 2, -34 };
System.out.println("Ascending Sorted Array: " + Arrays.toString(ascendingBubbleSort(array)) + "\n");
}

public static int[] ascendingBubbleSort(int[] array) {
Instant start = Instant.now();

//Bubble Sort Implementation in Ascending Order
for (int indexTobeSorted = array.length - 1; indexTobeSorted > 0; indexTobeSorted--) {
for (int index = 0; index < indexTobeSorted; index++) {
if (array[index] > array[index + 1]) {
swap(array, index, index + 1);
}
}
}

Instant end = Instant.now();
System.out.println("Elapsed time of ascendingBubbleSort: " + Duration.between(start, end).toNanos());
return array;
}

public static void swap(int[] array, int firstIndex, int secondIndex) {
if (firstIndex != secondIndex) {
int temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}
}
}

Output Bubble Sort Java Implementation in Descending Order

public class BubbleSort {
public static void main(String[] args) {
int[] array = { 18, 32, -11, 6, 68, 2, -34 };
System.out.println("Descending Sorted Array: " + Arrays.toString(descendingBubbleSort(array)) + "\n");
}

public static int[] descendingBubbleSort(int[] array) {
Instant start = Instant.now();

//Bubble Sort Implementation in Descending Order
for (int indexTobeSorted = array.length - 1; indexTobeSorted > 0; indexTobeSorted--) {
for (int index = 0; index < indexTobeSorted; index++) {
if (array[index] < array[index + 1]) {
swap(array, index, index + 1);
}
}
}

Instant end = Instant.now();
System.out.println("Elapsed time of descendingBubbleSort: " + Duration.between(start, end).toNanos());
return array;
}

public static void swap(int[] array, int firstIndex, int secondIndex) {
if (firstIndex != secondIndex) {
int temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}
}
}

Output Optimized Bubble Sort Algorithm

In the traditional bubble sort algorithm, we do comparisons even when the array is sorted, and which causes an increase in execution time. So, how can we make this more efficient?

In order to solve this problem, we can use one more variable which we can call as isSwapped and its default value will be false which means all indexes are sorted and no need to do any sorting more. In this way, we will decrease the execution time of the sorting operation.

Optimized Bubble Sort Implementation in Java

public class BubbleSort {
public static void main(String[] args) {
int[] array = { 18, 32, -11, 6, 68, 2, -34 };
System.out.println("Optimized Ascending Sorted Array: " + Arrays.toString(optimizedAscendingBubbleSort(array)) + "\n");
}

public static int[] optimizedAscendingBubbleSort(int[] array) {
Instant start = Instant.now();
boolean isSwapped = false;

//Optimized Bubble Sort Implementation in Ascending Order
for (int indexTobeSorted = array.length - 1; indexTobeSorted > 0; indexTobeSorted--) {
for (int index = 0; index < indexTobeSorted; index++) {
if (array[index] > array[index + 1]) {
swap(array, index, index + 1);
isSwapped = true;
}
}
//Nothing swapped that means array already sorted. Why should we do more sorting then?
//We finish the outer iteration with break.
if (!isSwapped) break;
}

Instant end = Instant.now();
System.out.println("Elapsed time of optimized ascendingBubbleSort: " + Duration.between(start, end).toNanos());
return array;
}

public static void swap(int[] array, int firstIndex, int secondIndex) {
if (firstIndex != secondIndex) {
int temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}
}
}

Output

As you can see below, the optimized bubble sort performs better than the original bubble sort algorithm. You can see the implementation details on the swtestacademy GitHub page. I will share the project link at the end of the article. The Complexity of Bubble Sort

In this part, I will explain the time and space complexity of the bubble sort algorithm.

Time Complexity

In the bubble sort algorithm, we compare the adjacent elements in each iteration for the index to be sorted. Let’s say the length of the array is n. In our case n is equal to 7. Number of comparisons become:

(n-1) + (n-2) + (n-3) +…..+ 1 = n(n-1)/2

Which is approximately the n2. Hence, the time complexity is O(n2) in BigO notation.

As you also saw that we have two iterations (two for loops) which is also another way to show us Bubble Sort has n*n=n2 time complexity.

We can also think about the worst-case and best-case scenarios.

Worst Case Time Complexity of Bubble Sort

When we do a sort in ascending order and the array is ordered in descending order then we will have the worst-case scenario. In this case, the worst-case complexity will be O(n2).

Best Case Time Complexity of Bubble Sort

When we do a sort in ascending order and the array is also already ordered in ascending order then we will have the best-case scenario because the array is already ordered as we wanted. In this case, the best-case complexity will be O(n).

Space Complexity

The space complexity of bubble sort is O(1) because we use an extra variable for swapping operations.

On the contrary, in the optimized bubble sort algorithm, we use two extra variables but the space complexity remains the same O(1).

Is Bubble Sort Stable Sorting Algorithm?

Yes, it is. Bubble sort is a stable sorting algorithm. As you have seen in the diagram below, the sorting algorithm is stable because the order of the squares is maintained when their values are the same. The square with green color and value 15 is positioned before the red 15 and in the same way green 30 is positioned before the red 30. They maintained their positions after sorting. This is a stable sorting. When Can We Use Bubble Sort?

Bubble sort is a simple and inefficient sorting algorithm. Its time complexity is not the best one. Thus, it can be used when the running time does not matter and when we work with a small dataset.

GitHub Project

Bubble Sort Implementation in Java

In this article, I have shared what bubble sort is, how it works, its complexities, and its implementations. I also tried to visualize the bubble sort algorithm with colorful diagrams to make it as clear as possible. I hope you enjoyed reading this article.

Other Sorting Algorithms Articles

See you in another article,