Introduction to Bubble Sort in Java
Bubble sort is one of the most commonly used algorithms for sorting data in Java. Sorting is done recursively comparing the adjacent numbers and shifting them in the increasing or decreasing order. This shifting of elements is done until all the digits are completely sorted in the required order. Bubble sort is the name because the elements of an array bubble are their way to start. Let us understand the bubble sort algorithm by taking an example.
Example: Consider an array of numbers [6 1 8 5 3] that need to be arranged in increasing order.
The bubble sort algorithm works in multiple iterations until it finds that all the numbers are sorted.
Iterations
Below are the iterations performed in Bubble Sort in Java which is as follows:
First Iteration
[6 1 8 5 3] – It starts by comparing the first two numbers and shifts the lesser number of the two to its right. Hence among 6 and 1, 1 is the smaller number that is shifted to the left and 6 to the right. [1 6 8 5 3] – Next, it compares the adjacent two numbers by shifting one position to the right. Here, number 6 is lesser than 8, and hence the same order is retained. [1 6 8 5 3] – Again, by shifting one position to the right, a comparison takes place between 8 and 5. Number 5 gets shifted to the left as it is smaller than 8. [1 6 5 8 3] – Here, the comparison takes place between numbers 8 and 3. Number 3 is shifted to the left since it is smaller than 8. [1 6 5 3 8] – This is the final result of the order after 1st iteration.Second Iteration
Since the numbers are still not completely increasing, the program goes for the second iteration.
[1 6 5 3 8] – Here, the comparison again starts from the first two digits of the first iteration result. It compares numbers 1 and 6 and retains the same order since 1 is smaller than 6. [1 6 5 3 8] – Here, numbers 5 and 6 are compared. The same order is retained as it is already in the required increasing order. [1 5 6 3 8] – A comparison occurs between numbers 6 and 3. Number 3 is shifted to the left as it is smaller than 6. [1 5 3 6 8] – Next, numbers 6 and 8 are compared with each other. The same order is retained as it is in an expected order. [1 5 3 6 8] – This is the final result after the second iteration. Still, we can notice that the digits are not completely arranged in their increasing order. Still, we need to exchange numbers 5 and 3 to get the final result. Hence the program goes for the third iteration.Third Iteration
[1 5 3 6 8] – the Third iteration starts by comparing the first two digits, 1 and 5. Since the order is as expected, it is retained the same. [1 5 3 6 8]- Next, the adjacent numbers 3 and 5 are compared. Since 5 is larger than 3, it is shifted to the right side. [1 3 5 6 8] – The iteration goes on to compare numbers 5 and 6, 6 and 8. Since it is in the required order, it retains the order. [1 3 5 6 8] – Finally, the iteration is stopped as the program traverses comparing each adjacent element and finds that all the digits are in increasing order.Since only 5 elements of an array needed to be sorted, it took only 3 iterations. As the elements in the array increase, the amount of iterations also increases.
Bubble Sort Implementation using Java
Below is the Java code, which implements the Bubble sort algorithm. (Note that the first position of an array in Java starts at 0 and continues in increments of 1, i.e., array[0], array[1], array[2], and it continues.)
Code:
import java.util.Scanner;
public class BubbleSort {
static void bubbleSort(int[] arraytest) {
int n = arraytest.length; //length of the array is initialized to the integer n
int temp = 0; //A temporary variable called temp is declared as an integer and initialized to 0
for(int i=0; i < n; i++){ // first for loop performs multiple iterations
for(int j=1; j < (n-i); j++){
if(arraytest[j-1] > arraytest[j]){ // if loop compares the adjacent numbers
// swaps the numbers
temp = arraytest[j-1]; // assigns the greater number to temp variable
arraytest[j-1] = arraytest[j]; // shifts the lesser number to the previous position
arraytest[j] = temp; // bigger number is then assigned to the right hand side
}
}
}
}
public static void main(String[] args) {
int arraytest[] ={23,16,3,42,75,536,61}; // defining the values of array
System.out.println("Array Before Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++){ // for loop used to print the values of array
System.out.print(arraytest[i] + " ");
}
System.out.println();
bubbleSort(arraytest); // array elements are sorted using bubble sort function
System.out.println("Array After Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++){
System.out.print(arraytest[i] + " "); // for loop to print output values from array
}
}
}Output:
Advantages and Disadvantages of Bubble Sort in Java
Below are the different advantages and disadvantages of bubble sort in java:
Advantages
- The code is very easy to write and to understand. Typically takes only a few minutes.
- Implementation is also very easy.
- Bubble sorting sorts the numbers and keeps them in in-memory hence saves a lot of memory.
Disadvantages
- This algorithm is not suitable for large datasets as the comparison takes a lot of time. The time it takes to sort input numbers increases exponentially.
- O(n^2) is the average complexity of Bubble sort, and O(n) is the best case complexity (best case is when the elements are sorted in the first place), where n is the number of elements.
Real-Time Applications
Since Bubble sort is capable of detecting minute errors in sorting, it is used in computer graphics. It is also used in the polygon filling algorithm, where the polygon’s vertices lining needs to be sorted.
Conclusion
This article saw how the Bubble sort algorithm works and how it can be implemented using Java programming. Bubble sort is a very stable algorithm that can be easily implemented for comparatively small datasets. It is a case of comparison algorithm and is used by novices due to its simplicity.
Recommended Articles
This is a guide to Bubble Sort in Java. Here we discuss multiple iterations to perform bubble sort in java and its code implementation along with advantages and disadvantages. You may also look at the following articles to learn more –
