Bubble Sort in Java – Learn How to Implement with Example!
Get Job-ready: Java Course with 45+ Real-time Projects! - Learn Java
Sorting is a technique used by programmers around the world to arrange a given set of data in either ascending or descending order. Sorting is an integral part of data structure and a concept that cannot be neglected by programmers. In this article, we will take a look at one such sorting method known as Bubble sort in java.
What is Bubble sort?
Bubble sort is a stable sorting algorithm. You might ask what is a stable sort, it basically means that if there are two same elements in the data set, the order of the elements will be retained even after sorting.
Bubble sort repeatedly checks all the elements and swaps them to either take the largest element to the end or bring the smallest element upfront. The mechanism of bubble sort remains the same, but the sorting might vary depending on the user’s needs.
Why the name Bubble Sort?
The name given to this sort is very unique due to its unique feature. Bubble sort brings all the smaller elements to the top of the list and takes the largest element to the end of the list. We can say, just how bubbles float upwards as they are lighter than air, in bubble sort as well the lighter elements move to the top. Hence the name Bubble Sort.
Bubble Sort Algorithm:
Let us now see how Bubble sort works through a simple algorithm.
Algo_BubbleSort(A, N) Step 1: Repeat for i in 0 to N Step 2: Repeat for j in 0 to N-i-1 Step 3: Check If A[j] > A[j+1] then Step 4: Swap A[j] and A[j+1] Step 5: End Inner Loop Step 6: End Outer Loop Step 7: End Process
Dry Run of the above algorithm(Working Example):
Let us consider the following list: 3 4 1 2 6 8 7
We will check only one full iteration in detail to understand the working of Bubble sort.
Iteration 1:
a. Compare 3 and 4, Since 3<4, No swapping.
b. Compare 4 and 1, Since 4>1, Swapping needed: 3 1 4 2 6 8 7
c. Compare 4 and 2, Since 4>2, Swapping needed: 3 1 2 4 6 8 7
d. Compare 4 and 6, Since 4<6, No swapping.
e. Compare 6 and 8, Since 6<8, No swapping.
f. Compare 8 and 7, Since 8>7, Swapping needed: 3 1 2 4 6 7 8
This was just one iteration of the outer loop, this continues for N-1 times, where N is the size of the Array.
We can see from the above example clearly, how the largest element, i.e. 8, gets swapped to the end of the array.
Implementing Bubble Sort to Arrange in Ascending Order:
package com.DataFlair.Bubblesort; class bubble_sort { public static void main() { int i,j,temp,n=7; int array[]={3,4,1,2,6,8,7}; for(i=0;i<n;i++) { for(j=0;j<n-i-1;j++) { if(array[j]>array[j+1]) { temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } } System.out.println("The array after sorting is: \n"); for(i=0;i<n;i++) { System.out.print(array[i]); } } }
Output:
1234678
Implementing Bubble Sort to Arrange in Descending Order:
package com.DataFlair.Bubblesort; class bubble_sort { public static void main() { int i,j,temp,n=8; int array[]={1,2,3,4,5,6,7,8}; for(i=0;i<n;i++) { for(j=0;j<n-i-1;j++) { if(array[j]<array[j+1]) { temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } } System.out.println("The array after sorting is: \n"); for(i=0;i<n;i++) { System.out.print(array[i]); } } }
Technology is evolving rapidly!
Stay updated with DataFlair on WhatsApp!!
Output:
87654321
Time and Space Complexity of Bubble Sort:
- The Best Case time complexity of bubble sort is O(n)
- The Worst-Case time complexity of bubble sort is O(n^2)
- The Average Case time complexity of bubble sort is O(n^2)
- The Space Complexity of bubble sort is O(n)
- The Auxiliary Space Complexity of bubble sort is O(1)
Optimization of Bubble Sort:
Consider the following scenario:
The given array contains: 1 2 3 4 5 6 7 8
We can see that the array is already sorted, we don’t need to run the algorithm at all. But due to the mechanism of the algorithm, the algorithm will still execute N-1 times.
Now, consider a scenario where the array is sorted after the first or second iteration, in that case as well, the program will run N-1 times. This is a major issue with respect to time complexity. Let us see how we can fix the above program to get the optimal time complexity.
Optimized Program for Bubble Sort:
package com.DataFlair.Bubblesort; class bubble_sort { public static void main() { int i,j,temp,n=8; boolean flag= false; int array[]={1,2,3,4,5,6,7,8}; for(i=0;i<n;i++) { flag = false; for(j=0;j<n-i-1;j++) { if(array[j]>array[j+1]) { flag=true; temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } if(flag==false) { System.out.println("The Array is Sorted"); break; } } System.out.println("The array after sorting is: \n"); for(i=0;i<n;i++) { System.out.print(array[i]); } } }
Output:
The array after sorting is:
12345678
As we can see, by adding a flag variable, we can optimize the bubble sort technique. The flag variable basically checks if there are any swapping operations happening in the inner loop and if there is no swapping, it means that the array is already sorted and we break out of the loop. This process reduces the complexity of the program by far and prevents unnecessary looping.
Use of Bubble Sort:
- Bubble sort is a simple yet useful sorting technique, it can sort a given set of data in linear time complexity for best-case scenarios.
- It can be used in greedy algorithms like Kruskal’s Algorithm to find the Minimal spanning tree in a graph.
- It can also be used in polygon filling algorithms, to detect very small errors in linear time complexity of 2n.
Advantages of Bubble Sort in Java:
1. Bubble sort is a basic sorting technique that requires a few lines of code and is very easy to understand.
2. It doesn’t use any complex algorithm techniques like Divide and Compare or Divide and Conquer.
3. It is a stable sort and thus the element’s memory location remains unchanged for equal value.
Disadvantages of Bubble Sort in Java:
1. For the average or worst-case scenario, bubble sort has a polynomial-time complexity of n^2 thus a data set with above a certain amount of elements will take forever to calculate even on a supercomputer.
2. Bubble sort works very slow on modern CPUs. It writes in the memory way more than any other sorting technique and produces even more cache misses.
Applications of Bubble Sort in Java
Despite its limitations, bubble sort can still be useful in certain scenarios. Here are a few examples:
1. Small Datasets: When dealing with very small datasets (less than 10 or 20 elements), bubble sort’s simplicity and ease of implementation can make it a suitable choice.
2. Educational Purposes: Due to its clear logic, bubble sort is often used as an introductory sorting algorithm in computer science courses. It helps students grasp the fundamental concepts of sorting before moving on to more complex algorithms.
3. Optimization Techniques: Bubble sort can be a building block for optimization techniques in other sorting algorithms. For instance, some sorting algorithms like insertion sort might utilize bubble sort for partially sorted arrays
Conclusion:
Bubble sort is the most commonly used algorithm for sorting due to its simplicity. In this article, we discussed in detail how bubble sort is implemented and how to optimize the bubble sort algorithm. We also discussed the uses of bubble sort and also the advantages and disadvantages of this sorting technique.
Did you know we work 24x7 to provide you best tutorials
Please encourage us - write a review on Google
Good explanation
Hi Yashi,
We are glad our reader liked our content. We recommend you to explore other Java tutorials as well, we have 100+ Java tutorials with a series of Java Interview Questions and quizzes. It will help you to brush up your skills,
Regards,
DataFlair