Last Updated on July 1, 2023 by Prepbytes
In this article, we will delve into the bubble sort algorithm and its implementation in Java. We will explore the intricacies of the algorithm, examine its time and space complexity, analyze the best and worst-case scenarios, and evaluate its stability. Without further ado, let us commence with our exploration.
What is Bubble Sort in Java?
Bubble Sort is an algorithm used to arrange the elements of an array or a list in either ascending or descending order. It is a comparison-based sorting algorithm, meaning that it relies on comparing the elements with each other to perform the sorting operation. You might be curious about how sorting can occur without directly comparing the elements.
Alternatively, there exists a different type of sorting known as Linear sorting, which does not involve comparisons. Examples of linear sorting include Count Sort and Radix Sort. However, these methods are beyond the scope of our current discussion.
In the bubble sort algorithm, during each iteration, the heaviest element "bubbles" its way to the end of the array. This implies that the first iteration identifies the maximum element, the second iteration finds the second maximum element, and so on (assuming the sorting is performed in ascending order). The steps of the bubble sort algorithm are as follows.
Bubble Sort Algorithm:
- There will be N-1 iterations i.e. the iteration variable i varies as 0<= i < N-1. In each iteration, follow these steps:
- Run a loop from 0 <= j < N-i+1.
- In this loop, compare the adjacent elements i.e. array[j] and array[j+1]. If array[j] > array[j+1], the bigger element is before the smaller one in the array. So, swap them. Else, move further.
- After these N-1 iterations, the array will be sorted.
Let us demonstrate a dry run of these steps. So, consider the array shown below.
We will now sort this array using bubble sort. So, the first iteration and its steps are shown below.
So, in the first pass of the first iteration, we compare the first 2 elements. Since 5 is smaller than 9 i.e. the smaller element is on the left and larger on the right, the elements are in sorted positions with respect to each other. Hence, we don’t swap them.
Next, we compare 9 and 8. Since 9 is greater than 8, we will swap these elements and now 8 will come before 9.
Next, 9 and 2 are compared and again 9 gets swapped with 2. Then we compare 9 and 1. Since 9 is greater than 1, we swap them. Now, we can see that the largest element of the array i.e. 9 is at its sorted position i.e. at the last of the array. This will happen in every iteration.
So, we have established a fact that in the ith iteration of bubble sort, the ith largest element will move to the ith position from the back of the array i.e. its sorted position.
This was just the 1st iteration. Let us do one more iteration. The second iteration swaps are shown below.
So, the box around the last element i.e. 9 shows that it is already in its sorted position and no element will be compared to 9. So, the first 2 elements i.e. 5 and 8 are compared. Since they are in sorted positions with respect to each other, no swaps take place.
Next, we compare elements 8 and 2. Since 8 is larger than 2, the swap takes place. Then, 8 and 1 are compared and since 8 is greater than 1, swapping takes place and 8 goes to the second last position of the array.
So, we got the second largest element at the second last position of the array in the second iteration of bubble sort.
This is how the complete bubble sort algorithm will continue for 4 iterations (as there are 5 elements and the number of iterations = N-1 = 5-1=4). The rest of the iterations are shown below.
So, we can see that after 4 iterations, the array got sorted. So, now that we have understood the logic, let us write the bubble sort program in Java.
Bubble Sort Program in Java
import java.util.*;
public class Main {
public static void bubbleSort(int arr[]) {
int n = arr.length;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
public static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String[] args) {
int[] arr = {5,9,8,2,1};
bubbleSort(arr);
for(int i=0;i<arr.length;i++) {
System.out.print(arr[i] + " ");
}
}
}
Time Complexity of Bubble Sort Program in Java:
The time complexity of the above program is O(n2) where n is the number of elements. This is because we are using a nested loop. The outer loop runs for n-1 iterations and the inner loop runs for n-i+1 iterations.
Space Complexity of Bubble Sort Program in Java:
Since we have not used any extra space, the auxiliary space used will be O(1).
Bubble Sort Program in Java – Optimized Version
The time complexity of the bubble sort algorithm, O(n^2), cannot be improved. However, there is a way to enhance the algorithm. In the program provided above, the bubble sort algorithm completes n-1 iterations even if the array is already sorted. Nevertheless, we can modify it to perform only one iteration. If no swaps are made during this iteration, it indicates that the array is already sorted. Consequently, we can avoid further iterations. The modified version of the program, incorporating this change, is presented below.
Bubble Sort Program in Java – Optimized Version
import java.util.*;
public class Main {
public static void bubbleSort(int arr[]) {
int n = arr.length;
boolean flag = false;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
if(flag == false) break;
}
}
public static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String[] args) {
int[] arr = {5,9,8,2,1};
bubbleSort(arr);
for(int i=0;i<arr.length;i++) {
System.out.print(arr[i] + " ");
}
}
}
Time Complexity of Optimized Bubble Sort Program in Java:
The time complexity is still the same. However, the best-case time complexity has improved, but the overall time complexity is still O(n2).
Space Complexity of Optimized Bubble Sort Program in Java:
The space complexity is also the same i.e. O(1).
Best Case of Bubble Sort Program in Java
From the optimized version of bubble sort, we can say that the best case of the bubble sort is when the array is already sorted as then we only have to perform 1 iteration on the array. Hence, the best case of bubble sort is when the input array is already sorted and the best case time complexity is O(N) where N is the number of elements.
Worst Case of Bubble Sort Program in Java
The worst case of the Bubble Sort algorithm is when the array is reverse sorted. This is because if the array is reverse sorted i.e. if we want to sort in ascending order and the array is in descending order or vice versa, then the bubble sort algorithm will perform the maximum number of comparisons and swaps. So, the worst case of the bubble sort algorithm is if the array is reverse sorted and the worst case time complexity is O(n2).
Is Bubble Sort Stable?
Yes, Bubble sort is a stable algorithm. What do we mean by stability? Consider the array shown below.
There are two 2s in the array. One is named 2a and the other as 2b. Before sorting, element 2a is before element 2b. After sorting also, we want 2a to be before 2b. If a sorting algorithm is able to maintain the order between the equal elements as it was before sorting, then that algorithm is a stable sorting algorithm.
Conclusion
In conclusion, bubble sort is a simple yet inefficient sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order. Despite its simplicity, it has a time complexity of O(n^2), making it less suitable for large data sets. However, it can still be useful for small arrays or in situations where simplicity is prioritized over efficiency.
FAQs related to bubble sort in Java:
Q1. Can bubble sort be used for sorting objects other than integers?
Yes, bubble sort can be used to sort objects of any comparable type. You need to implement the comparison logic by overriding the compareTo method or by providing a custom comparator.
Q2. How does bubble sort compare to other sorting algorithms like merge sort or quicksort?
Bubble sort has a higher time complexity compared to more efficient algorithms like merge sort or quicksort. It is generally considered as a simple algorithm for educational purposes or when dealing with small data sets.
Q3. Is bubble sort stable?
Yes, bubble sort is a stable sorting algorithm. It preserves the relative order of elements with equal values. If two elements are equal, their original order will be maintained after sorting.
Q4. Can bubble sort be used for sorting a linked list?
Bubble sort can be applied to sort a linked list by swapping the nodes instead of array elements. However, due to its time complexity, it is not recommended for large linked lists.
Q5. Are there any optimized versions of bubble sort?
Yes, there are variations of bubble sort such as the optimized bubble sort or the cocktail shaker sort. These variations introduce enhancements to reduce the number of iterations or optimize the swapping process.
Other Java Programs
Java Program to Add Two Numbers
Java Program to Check Prime Number
Java Program to Check Whether a Number is a Palindrome or Not
Java Program to Find the Factorial of a Number
Java Program to Reverse a Number
Java Program to search an element in a Linked List
Program to convert ArrayList to LinkedList in Java
Java Program to Reverse a linked list
Java Program to search an element in a Linked List
Anagram Program in Java
Inheritance Program in Java
Even Odd Program in Java
Hello World Program in Java
If else Program in Java
Binary Search Program in Java
Linear Search Program in Java
Menu Driven Program in Java
Package Program in Java
Leap Year Program in Java
Array Programs in Java
Linked List Program in Java
String Programs in Java
Star Program in Java
Number Pattern Program in Java
For Loop Program In Java
Pattern Program in Java
String Palindrome Program in Java
Thread Program in JAVA
Java Scanner Program
While Loop Program in Java