Bubble Sort Algorithm in Java
We always use sorting as a fundamental operation in real world web applications, such as sorting by price, reviews, number of likes, quantity, received time etc.
Some sorting algorithms are easy to understand but not very efficient, and there are some algorithms that are not simple to understand but efficient.
There are some popular sorting algorithms
ex => bubble sort, quick sort, selection sort, insertion sort, merge sort, heap sort, bucket sort
bubble sort is known as the simplest sorting algorithm. when we need to arrange some elements or list of items in ascending order, we use bubble sort.
It is very easy to understand, but it is not a very efficient or fast algorithm. This is not very useful when you handling large datasets, such as arrays with numerous elements.
Sorting methodology
Let’s learn the concept of bubble sort using Java code.
If you want to sort items, elements or numbers in order, initially have to store them somewhere.
For that, you can store them in an array. Now you have an array of elements which you want to sort.
Consider an integer array with 6 elements indexed starting at 0.
In this case, the array’s length is 6. The algorithm operates by comparing 2 values at a time, starting from the beginning of the array, and check which is larger and swap them.
Here’s how it works.
- Take the first 2 values in the array, then compare. If the 1st value is greater than the 2nd, you swap them.
- Otherwise, leave them unchanged.
- Next compare the 2nd and the 3rd values.
- If the 2nd value is greater than the 3rd, you swap them.
- Then you compare the 3rd and the 4th values.
- If the 3rd value is greater than the 4th, you swap them.
- You should shift through the array, repeating the same step until reach the end of the array.
Basically, what we do here is repeatedly swapping the adjacent elements if they are in the wrong order.
After completing the first iteration, the largest value will be positioned at the end of the array.
But the rest of the array remains unsorted.
You must follow this same approach for multiple iterations until you get the full array sorted. Number of iterations you must perform depends on the length of the array. (precisely iterations = array length — 1)
In the first iteration, you perform 6 comparisons, but in the second iteration, you only need 5 because the last value is already sorted from the previous iteration.
In the next iteration, you only need 4 comparisons because the last 2 values are sorted in previous iterations. Subsequent iterations require fewer comparison.
Once you completed all iterations, your array is fully sorted.
- In some cases, after only completing 3 or 4 iterations, we can see the array get fully sorted.
- But the algorithm is not aware of that. algorithm checks from start to end repeatedly.
- Therefore, we have to continue checking the rest of the array, even if they are already sorted.
- Since the rest is already sorted, the algorithm doesn’t swap values but keeps checking.
- As a result, it spends unnecessary effort checking and comparing values, which contributes to its inefficiency. That is one of the major drawbacks in bubble sort.
Best time complexity for Bubble Sort is O(n) while the average and worst time complexity is O(n²).
Let’s declare an integer array with 6 elements and implement the sorting logic using 2 for loops (nested for loop):
int nums[] = {5, 1, 6, 2, 4, 3};
int size = nums.length;
for (int i = 0; i < size; i++) {
// outer for loop
for (int j = 0; j < size - 1; j++) {
// inner for loop
}
}While outer for loop is handling iterations, inner for loop handles checking and swapping
Get Ravithamara’s stories in your inbox
Join Medium for free to get updates from this writer.
In the inner for loop => current value is represented by nums[j] and next value is represented by nums[j+1]
How to compare these 2 values => if( nums[j] > nums[j+1] )
int nums[] = {5, 1, 6, 2, 4, 3};
int size = nums.length;
for (int i = 0; i < size; i++) {
// outer for loop
for (int j = 0; j < size - 1; j++) {
if(nums[j] > nums[j+1]){
}
// inner for loop
}
}How to swap adjacent elements => for that, you can use a temporary variable called temp.
// swapping values
temp = nums[j]
nums[j] = nums[j+1]
nums[j+1] = temp
int nums[] = {5, 1, 6, 2, 4, 3};
int size = nums.length;
int temp = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size - 1; j++) {
if (nums[j] > nums[j + 1]) {
temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp; // Swapping elements
}
}
}As discussed, after each iteration, one value is sorted, reducing the number of values that need to be checked in subsequent iterations. Therefore the inner loop’s range should be j < size - i - 1 instead of j < size - 1. This adjustment will not change the output, but it will increase the speed by avoiding unnecessary checks of already sorted values.
j < size - i - 1 approach takes less time comparing to j < size - 1 approach.
int nums[] = {5, 1, 6, 2, 4, 3};
int size = nums.length;
int temp = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp; // Swapping elements
}
}
}Final completed code in Java main class
public class BubbleSort{
public static void main(String[] args) {
int nums[] = {5, 1, 6, 2, 4, 3};
int size = nums.length;
int temp = 0;
System.out.println("before sorting");
for(int num : nums){
System.out.println(num); //printing array
}
System.out.println();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp; // Swapping elements
}
}
}
System.out.println("after sorting");
for(int num : nums){
System.out.println(num); //printing array
}
}
}Output will be
before sorting 5,1,6,2,4,3 after sorting 1,2,3,4,5,6
We can also use a different way to print array in for loop (optional. Both are correct
System.out.println(“before sorting”);
for(int num : nums){
System.out.println(num); //printing array
}System.out.println(“after sorting”);
for(int num : nums){
System.out.println(num); //printing array
}
Instead of above, we can use
System.out.println(“before sorting”);
for(int n=0; n < size; n++){
System.out.print(nums[n] + “ “);
}System.out.println(“after sorting”);
for(int n=0; n < size; n++){
System.out.print(nums[n] + “ “);
}
