Bubble Sort in Java - Naukri Code 360

Q: 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.

Introduction

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.

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.

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

Use two loops to iterate through the input array.
The outer loop runs from i=0 to i=n-2.
The inner loop runs from j=0 to j=n-i-2;
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.

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.

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.

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.

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.

So, the final list will look like this after the 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.

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));
  }
}

You can also try this code with Online Java Compiler

Run Code

Output

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

You can also try this code with Online Java Compiler

Run Code

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));
  }
}

You can also try this code with Online Java Compiler

Run Code

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(n²)
Average Case	O(n²)
Best Case	O(n)

The time complexity of the bubble sort algorithm is O(n²), 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(n²).

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(n²) operations.

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.

What is bubble and insertion sort in Java?

Bubble Sort repeatedly compares adjacent elements and swaps them if they're in the wrong order, sorting the array step by step. Insertion Sort builds a sorted portion by picking elements and inserting them in the correct position.

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 n times.

Conclusion

Bubble Sort is a simple and easy-to-implement sorting algorithm in Java, ideal for small datasets or when simplicity is valued over efficiency. However, due to its O(n²) time complexity, it is not suitable for large or performance-critical applications. For more efficient sorting, algorithms like Quick Sort or Merge Sort are preferred. We hope this blog has helped you enhance your knowledge of bubble sort java.

Check out these useful blogs: