Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a bubble sort in Java?
3.
Bubble Sort Algorithm
4.
Steps Required to Follow for Bubble Sort in Java
5.
How does Bubble Sort in Java Work?
5.1.
First Iteration (Compare and Swap)
5.2.
Remaining Iteration
6.
Implementation of Bubble Sort Java
6.1.
Java
6.2.
Output
7.
Optimized Bubble Sort Algorithm
7.1.
Optimized Code for Bubble Sort Java
7.2.
Java
8.
Time Complexity of Bubble Sort in Java
9.
Space Complexity of Bubble Sort in Java
10.
Advantages of Bubble Sort in Java
11.
Disadvantages of Bubble Sort in Java
12.
Bubble Sort Java Applications
13.
Frequently Asked Questions
13.1.
What are bubble sort and binary search in Java?
13.2.
Why two loops are used in bubble sort?
13.3.
How to sort a 2D array using bubble sort in Java?
13.4.
What is an example of bubble sort?
13.5.
How to make a bubble sort algorithm in Java?
14.
Conclusion
Last Updated: Mar 27, 2024
Easy

Bubble Sort in Java

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Hello, Ninja! Do you recall your school days? We used to stand on the ground for exercise during morning assembly. Our teachers used to classify students based on their height. 

bubble sort java

Have you ever considered how important Sorting is in the programming world?

Sorting is almost applicable everywhere you see. Even the contact list in your phone is sorted, which entails that you can easily access your contact from your phone since the data is arranged in that manner for you. In other words, “it is sorted”.

In simple words, sorting is arranging the items in a sorted manner according to some condition. 

So, what’s for today? 

Today we will discuss one of the most famous sorting algorithms:Bubble Sort. We will also be looking at its implementation in Java

What is a bubble sort in Java?

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the entire list is sorted. While straightforward to implement, bubble sort is inefficient for large lists and is mainly used for educational purposes or when dealing with small datasets.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Bubble Sort Algorithm

In the Bubble sort algorithm, we sort an unsorted array by starting from the first element and comparing it with the adjacent element. If the former is greater than the latter, we swap and get the largest number at the end of the first iteration. Basically, in the bubble sort, elements gradually "bubble" (or rise) to their proper location in the array as they are sorted, much like soda bubbles rising in a glass.

The bubble sort compares adjacent array elements repeatedly. If the first and second elements are out of order, they switch positions. Next, if the second and third elements are out of order, they are compared and switched, and so on.

Steps Required to Follow for Bubble Sort in Java

Below are the steps required to follow for Bubble Sort Java

  1. Use two loops to iterate through the input array. 
     
  2. The outer loop runs from i=0 to i=n-2.
     
  3. The inner loop runs from j=0 to j=n-i-2;
     
  4. For every j, compare arr[j] and arr[j+1]. If arr[j]>arr[j+1], then swap them or else move forward. 

How does Bubble Sort in Java Work?

Bubble Sort is based on repeatedly checking adjacent elements and swapping them if they are in the wrong order. Let us understand Bubble Sort with the help of an example.

Suppose there is an array of 5 elements [6, 3, 7, 2, 9]. We need to sort the array in ascending order. We will use the above concept of Bubble sort to do so. 

sample array

First Iteration (Compare and Swap)

A and B will be compared and checked to see if they are in correct order or not. 

As you can see in the image above, B is smaller than A, hence swapping will be performed here. 

first iteration

A and C will be compared in the same way A and B are compared. This time you guess whether swapping will happen or not. 

first iteration

Since C is greater than A, henceforth no swapping.

C and D will be compared now. As it is seen in the image above, D is smaller than C, swapping will happen. 

first iteration

Finally, we have only 2 elements to compare, i.e., C and E. It is clearly seen that E is taller than C; hence no swapping will be performed.

first iteration

So, the final list will look like this after the first Iteration. 

first iteration

After each Iteration, the largest element will be placed in the right position. In the above example, E is the largest element and is in the right place. 

Remaining Iteration

We'll do the same thing we did in the first pass: Check adjacent elements and place them in the correct order, beginning with the first.

We already know that the last element is correctly placed, so we won't compare it to the second-last element.

  • After the second pass, we can be sure that the element in the second-to-last position is in the correct position.
     
  • After each pass, at least one element from the unsorted part of the array is placed in its proper position. To sort our array, we must make n - 1 passes, where n is the size of our array.
final array

In the next section we will discuss the implementation of Bubble Sort in Java.

Implementation of Bubble Sort Java

  • Java

Java

// Java Implementation of Bubble Sort Algorithm
import java.util.Arrays;

class Main {
 static void bubbleSortAlgorithm(int array[]) {
   int size = array.length;
   
   for (int i = 0; i < size - 1; i++)
   
     for (int j = 0; j < size - i - 1; j++)
     
       if (array[j] > array[j + 1]) {
         int temp = array[j];
         array[j] = array[j + 1];
         array[j + 1] = temp;
         
       }
 }
 
 public static void main(String args[]) {
   int[] data = { 6, 5, 8, 1, 2 };
   
   bubbleSortAlgorithm(data);
   
   System.out.println("The array performing the Bubble Sort Algorithm is:");
   System.out.println(Arrays.toString(data));
 }
}

Output

The array performing the Bubble Sort Algorithm is:
[1, 2, 5, 6, 8]

Optimized Bubble Sort Algorithm

In the typical bubble sort algorithm, the outer loop continues to execute even if we don't perform any swap operation in the inner loop. So, there will be no swapping if the elements are already sorted. 

To avoid these unnecessary comparisons, we can keep a flag set to false. If any swap is performed, it is set to true; otherwise, it remains false. 

Then at each iteration of the outer loop, we need to check if the flag is false, we break the loop, or else we continue. 

In the next section, we will see the implementation of the bubble sort algorithm along with the space and time complexity. 

Optimized Code for Bubble Sort Java

  • Java

Java

// Java Implementation of Bubble Sort Algorithm
import java.util.Arrays;

class Main {
 static void bubbleSortAlgorithm(int arr[]) {
 
   int len = arr.length-1;
   
   for (int i = 0; i < len; i++){
   
       // check if swapping occurs
       boolean isSwap = false;
       
     for (int j = 0; j < len - i; j++){
     
       if (arr[j] > arr[j + 1]) {
         int temp = arr[j];
         
         arr[j] = arr[j + 1];
         arr[j + 1] = temp;
         isSwap = true;
       }
     }
     
     // no swapping means the array is sorted already
     // so no need for further comparison
     if (!isSwap)
       break;
   }
}

 public static void main(String args[]) {
   int[] data = { 6, 5, 8, 1, 2 };
   
   bubbleSortAlgorithm(data);
   
   System.out.println("The array performing the Bubble Sort Algorithm is:");
   System.out.println(Arrays.toString(data));
 }
}

Output

The array performing the Bubble Sort Algorithm is:
[1, 2, 5, 6, 8]

Time Complexity of Bubble Sort in Java

Case Time Complexity
Worst Case O(n2)
Average Case O(n2)
Best Case O(n)

The time complexity of the bubble sort algorithm is O(n2), where n is the number of elements present in the given array.

You can see that we use two nested loops for sorting. The inner loop can run up to n times, and the outer loop can also run up to n times in the worst case. Hence, the total number of comparisons will be O(n*n); thus, time complexity will be O(n*n) which is O(n2).

The best case occurs when the array is already sorted. So, the best case time complexity is O(n), as we need at least a single pass to know that no swapping has been performed. 

The worst case occurs when the array elements are sorted in reverse order, which implies that the algorithm will not finish before O(n2operations.

Space Complexity of Bubble Sort in Java

The space complexity of the bubble sort java algorithm is O(1)

Since the algorithm uses only a constant amount of space for the loop variables and an extra variable to store the swapping status.

Moreover, bubble sort is an in-place sorting algorithm that manipulates the original array for sorting. 

Advantages of Bubble Sort in Java

Bubble Sort is one of the most famous sorting algorithms due to the following reasons.

  • The primary advantage of the bubble sort is that it is popular and easy to implement. 
     
  • In the bubble sort, elements are swapped in place without using additional temporary storage. 
     
  • The space requirement is at a minimum.

Disadvantages of Bubble Sort in Java

Despite having many advantages, Bubble Sort still has some disadvantages. Some of these disadvantages are listed below.

  • The main disadvantage of the bubble sort is that it does not deal well with a list containing a huge number of items. 
     
  • The bubble sort requires N2 processing steps for every N number of elements to be sorted. This makes it much slower as compared to other sorting algorithms like Merge Sort and Quick Sort.
     
  • The bubble sort algorithm is unsuitable for real-life applications.

Bubble Sort Java Applications

  • Learning Purpose: Bubble Sort is used for learning purposes to learn sorting algorithms and their basic principles.
     
  • Debugging and Testing: During the debugging phases of various applications, bubble sort can be used to check if the elements in an array are sorted correctly.
     
  • Small Lists: If you have only a few things to sort, Bubble Sort is simple enough to use. It's like organizing a handful of cards.
     
  • Prototypes: For early versions of a program or when testing ideas, Bubble Sort can be a fast and simple way to sort things.
     
  • Visualize Other Algorithms: If you're new to programming, practising Bubble Sort helps you understand how computers sort things, like organizing your room.

Frequently Asked Questions

What are bubble sort and binary search in Java?

Bubble Sort is a famous sorting algorithm in Java to sort an array in quadratic time complexity. On the other hand, Binary search is an algorithm to find an element in various logarithmic time complexity.

Why two loops are used in bubble sort?

Two loops are used in bubble sort: an outer loop to traverse the entire array repeatedly until no swaps are needed, and an inner loop to compare adjacent elements and perform swaps if necessary, ensuring proper sorting.

How to sort a 2D array using bubble sort in Java?

To sort a 2D array using bubble sort in Java, iterate through each row of the array and apply bubble sort to each row individually. This involves performing comparisons and swaps within each row, similar to sorting a 1D array, until the entire 2D array is sorted.

What is an example of bubble sort?

Bubble sort is slower as compared to other sorting algorithms like Merge Sort. Hence it is used for sorting smaller datasets. An example of bubble sort could be to sort an array of 5 elements [5, 4, 6, 9, 2].

How to make a bubble sort algorithm in Java?

First, we can iterate through the whole array to make a bubble sort algorithm in Java. We check and swap the adjacent elements in each iteration if they are in the wrong order. We continue this process times.

Conclusion

In this article, we discussed bubble sort java from scratch, starting with the introduction followed by the working of the algorithm with the help of an example. We also learned the optimized bubble sort algorithm's implementation and the time and space complexity analysis. 

We hope this blog has helped you enhance your knowledge of bubble sort java. 
 

Check out these useful blogs - 

Do upvote our blog to help other ninjas grow.

Happy Coding!‍