Java Bubble Sort Working and Example
Sorting generally means to sort or order a particular array or collection of elements into a particular sequence i.e either in ascending order or in descending order.
There are many kinds of Sorting techniques to sort a given array of numbers. In this article, we will learn the Bubble Sort technique in Java. It is one of the most used techniques for Sorting.
We will discuss it with its working and also we will implement it in Java to sort the array in both ascending and descending orders. So, without wasting time, let’s start discussing what Bubble Sort is.
What is a Bubble Sort?
Bubble Sort is one of the simplest sorting techniques in Java to sort the array elements.
The idea is to traverse from the starting element to the last one by comparing the adjacent elements and swapping them if they are not in the specific order.
It is called Bubble sort because, at the end of each iteration, the largest number sits at the bottom of the array just like the heaviest bubble settles down in a vessel. The swapping of elements continues until the array is sorted and no more swapping is required.
We can also sort the elements in the descending order in which the smallest element goes at the end of the array in each iteration. This can only happen if we inverse the weight of the element.
Some important points about the Bubble sort are:
1. The Worst and Average case complexity of Bubble Sort is O(n2), where n denotes the total number of elements in the array.
2. The Best case complexity of Bubble sort is O(n), where n is the number of elements in the array. This case can happen only when the given array is already sorted.
3. The Auxiliary space consumed by the bubble sort algorithm is O(1)
4. The Bubble Sort is a type of in Place Sorting.
5. Bubble sort is a Stable Algorithm.
Note: We can optimize the algorithm of Bubble sort and reduce our complexity to the order of “n” (O(n)) by adding some extra lines of code to the original code.
If the user entered a sorted array, so, rather than applying for all the passes we can just apply for a single pass and check whether any swap occurs during the whole pass.
If there are no swaps occurring in the whole pass then we stop the algorithm and return the original array. By adding this piece of code we can ensure to enhance our performance of the algorithm and also reduce the time complexity.
Working of Bubble Sort in Java
Now, we will see how the Bubble Sort in Java works with the given array. We have an array and to sort it, there are 4 iterations after which we will get a sorted array.
The following diagram illustrates the working of a Bubble sort
Bubble Sort Program in Java to sort a given array in ascending order
package com.techvidvan.bubblesort;
public class BubbleSortDemo {
static void bubbleAscending(int[] myarray) {
int n = myarray.length;
int temp = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < (n - i); j++) {
if (myarray[j - 1] > myarray[j]) {
//Code to swap the elements
temp = myarray[j - 1];
myarray[j - 1] = myarray[j];
myarray[j] = temp;
}
}
}
}
public static void main(String[] args) {
int myarray[] = {
4,
15,
12,
21,
2,
25,
10,
18
};
System.out.println("Array on which we apply Bubble Sort: ");
for (int i = 0; i < myarray.length; i++) {
System.out.print(myarray[i] + " ");
}
System.out.println();
bubbleAscending(myarray); //Applying Bubble sort to sort the Array
System.out.println("Array after applying Bubble Sort: ");
for (int i = 0; i < myarray.length; i++) {
System.out.print(myarray[i] + " ");
}
}
}
Output:
Array on which we apply Bubble Sort: 4, 15, 12, 21, 2, 25, 10, 18
Array after applying Bubble Sort: 2, 4, 10, 12, 15, 18, 21, 25
Java Bubble Sort Example to sort a given array in Descending order
package com.techvidvan.bubblesort;
public class BubbleSortDemo {
static void bubbleDescending(int[] myarray) {
int n = myarray.length;
int temp = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < (n - i); j++) {
if (myarray[j - 1] < myarray[j]) {
//Code to swap the elements
temp = myarray[j - 1];
myarray[j - 1] = myarray[j];
myarray[j] = temp;
}
}
}
}
public static void main(String[] args) {
int myarray[] = {
4,
15,
12,
21,
2,
25,
10,
18
};
System.out.println("Array on which we apply Bubble Sort: ");
for (int i = 0; i < myarray.length; i++) {
System.out.print(myarray[i] + " ");
}
System.out.println();
bubbleDescending(myarray); //Applying Bubble sort to sort the Array
System.out.println("Array after applying Bubble Sort: ");
for (int i = 0; i < myarray.length; i++) {
System.out.print(myarray[i] + " ");
}
}
}
Output:
Array on which we apply Bubble Sort: 4, 15, 12, 21, 2, 25, 10, 18
Array after applying Bubble Sort: 25, 21, 18, 15, 12, 10, 4, 2
Use of Java Bubble Sort
As the Bubble Sort technique is the simplest sorting technique, it is often used in many areas of software technologies.
For example, the Bubble Sort is very useful in the field of Computer graphics where it can be used to detect a very small error for example swap between two elements and fix the error with a linear complexity of 2n, where n is the number of elements in the array.
Advantages of Bubble Sort in Java
The advantages of bubble sort are:
- It is simple to write and easy to understand
- It takes only a few lines of code
- Bubble sort is an in-place sorting technique, therefore the data is in the memory, and therefore there is minimal memory overhead.
Disadvantages of Java Bubble Sort
There are also some drawbacks of bubble sort which are:
- It takes more amount of time to sort the array elements.
- The average time complexity increases with the increase in the number of elements of the array.
Conclusion
In this article, we studied what Bubble Sort is in Java and how we can use it to sort the array elements in a particular order. It is very easy to understand.
But we can conclude that it works best with the small arrays and its performance degrades as the number of array elements grows.We learned to sort an array in ascending as well descending order with the help of a Java program.
We can also increase the performance and efficiency of the bubble sort algorithm by adding a few lines of code to the original code. This article will surely help you become a master in the Bubble Sort technique in Java.