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 1^{st} 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 2^{nd} 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 3^{rd} 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 4^{th} 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 5^{th} 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 6^{th} 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 n^{2}. Hence, the **time complexity is O(n ^{2}) 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=n ^{2 }**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(n ^{2})**.

**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,

Onur Baskirt

Onur Baskirt is a senior IT professional with 15+ years of experience. Now, he is working as a Senior Technical Consultant at Emirates Airlines in Dubai.