Bubble Sort Program in Java – Explained with Examples

In this article, we will learn about the bubble sort algorithm and how to implement it step by step in the Java programming language. Bubble Sort is one of the simplest algorithms to understand and implement. This article will explore the bubble sort, its mechanics, and its implementation in Java and provide some examples to solidify our understanding.

What is Bubble Sort?

The simplest sorting algorithm repeatedly steps through the list or array. This algorithm compares the adjacent elements and swaps them if they are in the wrong order. This process continues until no swaps are needed, indicating that the list has been sorted.

Let’s see how the bubble sorting algorithm works.

• Run the two loops that are nested in one another.
• The outer loop will run from i=0 to i< n-1, where n is the number of elements listed.
• There is one more loop, which is run on the inner loop j=0 to j< n -i -1. It is because, after each iteration of the outer loop, one another element at the end (or at the start if the order is decreasing order) will be in its right place, so we can leave it as is. Then, we will check if the arr[j] > arr[j+1]. If it’s true, then we will swap places at these elements. If the condition is false, we will continue with the next iteration.  This process will be repeated till the conditions of the loop are not satisfied.
• This process will be repeated till the conditions of the loop are not satisfied.

For Decreasing, we have to change this thing in our bubble sort algorithm.

• This inner loop will run from j = i to j< n-1.
• We will compare the elements as arr[j] < arr[j+1]

The following program demonstrates the Bubble Sort in Java:

Program

Output

Complexity Analysis of Bubble Sort:

Time Complexity: O(N2), where N is the number of the items in the list

Auxiliary Space: O(N)

Working of Bubble Sort in Java

This section explains how the Bubble Sort Algorithm works.  Let’s sort an unsorted array using the Bubble Sort Array.

Let’s take the example of an array.

First Iteration

In the first iteration, we will compare the initial two elements to check whether the first element is greater or less in an array.

In this array, 32 is greater than the first element of the array, which is 13. So it is already sorted. We don’t need to sort them.

In this array, 26 is smaller than 32. Then, we will swap. After swapping, the new array will look like this.

Now, we compare 32 and 35.

Now, 35 is greater than 32. So, no swapping is required in this new sorted array. Let’s compare it to between 35 and 10..

Second Iteration

The same process will be followed in the second phase of iterations. 

Here, we will see that ten is smaller than 32. So, swapping will be performed. After swapping, the array will be.

Let’s move to the third iteration in the loop.

Third Iteration

The same process will be followed for the third iteration in this section.

10 is smaller than 26, so I will swap them. After swapping, the array will look like this.

Now, let’s move to the fourth iteration.

Fourth Iteration

In the fourth iteration, the array will look like this.

Here, we don’t need to swap any element. This array is already sorted.

Implementation of Bubble Sort in Java

In this section, we will implement the bubble sort algorithm in Java, which sorts a list.

The following program demonstrates Bubble Sort in Java:

Program

Output

Advantages of Bubble Sort in Java

The advantages of Bubble Sort in Java without number formatting:

• Simplicity: The Bubble sort algorithm is easy to understand and implement, making it accessible for beginners.

• No Extra Memory Usage: The bubble sort operates in place, requiring no additional memory beyond the original array, leading to a space complexity of O(1).

• Stable Sorting: It maintains the relative order of equal elements, which can be important in applications where the order matters.

• Education Value: Bubble sort is the foundational algorithm for learning basic sorting concepts and understanding algorithm design.

Disadvantages of Bubble Sort in Java

The bubble sort algorithm also has some disadvantages:

• High Number of Comparisons: The algorithm performs many comparisons and swaps, which can lead to significant overhead and slower performance as the dataset grows.

• Not Cache-Friendly: The bubble sort may not efficiently utilize CPU cache due to its repeated access patterns, which can further hinder performance.

• Increased Development Time: Developers may need to spend additional time implementing and optimizing bubble sort for specific use cases, even though better alternatives exist.

Also Read: Call by Value and Call by Reference in Java

Conclusion

It is a very simple sorting algorithm that introduces the concept of sorting and algorithm design. It is a comparison-based algorithm design. Being a comparison-based algorithm, comparison and swap of adjacent elements make it understandable, which is one of the many reasons it is often used for didactic purposes. It is a very valuable sorting algorithm for understanding the other algorithmic principles. It is essential to recognize its constraints and consider more efficient alternatives for practical use. Understanding bubble sort sets the groundwork for exploring more complex algorithms.