Bubble Sort is the elementary sorting algorithm for sorting various data structures. It is a comparison-based sorting algorithm in which each element is compared with the next element, and is swapped if those elements are not in the correct order.
The algorithm starts with comparing the first pair of elements.
If the first element is smaller than the second element, then the elements are swapped
This algorithm is not suitable for large data sets
Time Complexity
O(n2)
Best Case
O(n)
Worst Case
O(n2)
Space Complexity
O(1)
Avg. Comparisons
n(n-1)/2
Implementation of bubble sort in Java
First, we will take starting two elements from the list.
Then we will compare those elements.
If these elements are found in unsorted order we will sort them.
Else we will compare next to elements.
We will repeat the previous steps until we get our sorted array.
Let’s take an example, we have a list of number stored in array
This is called as bubble sort as you can see in each pass we get the largest element, which pushes (bubbles) towards the right always. Just like in a soda the largest bubble traverse to top of first.
// Time Complexity : O(N^2)
// Space Complexity : O(1)
class Main
{
static void bubbleSort(int a[])
{
int len = a.length; // calculating the length of array
for (int i = 0; i < len-1; i++)
for (int j = 0; j < len-i-1; j++)
if (a[j] > a[j+1]) //comparing the pair of elements
{
// swapping a[j+1] and a[i]
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
/* Prints the array */
static void printArray(int a[])
{
int len = a.length;
for (int i = 0; i < len; i++)
System.out.print(a[i] + " "); //printing the sorted array
System.out.println();
}
// Main method to test above
public static void main(String args[])
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);//calling the bubbleSort function
System.out.println("Sorted array");
printArray(arr); //calling the printArray function
}
}
Output
Sorted array
11 12 22 25 34 64 90
Bubble Sort Method 2 (Optimized)
The issue with previous algorithm was that it will always run all passes and iterations. Even if the arrays are already sorted, nearly sorted or not sorted.
We need to optimize the previous algorithm so that if the array becomes sorted at some time. We do not implement the algorithm further and print the array right then and ther.
ExampleArr [] = {1, 2, 3, 4, 5, 6, 7}
As you can see the array is sorted already, but our algorithm(previous) will run all iterations and passes anyways
Arr [] = {1, 2, 3, 4, 5, 10, 7}
The above array is nearly sorted, just 10 out of place. However, in pass 1 itself the array will get sorted but previous algorithm will still run all the passes
How it is solved?We can solve the above issue by bringing another boolean variable called swapped.
If in any pass no swapping happens, it means the array has become sorted and we do not need to run any further passes.
// Time Complexity : O(N^2)
// Space Complexity : O(1)
class Main
{
static void bubbleSort(int a[])
{
int len = a.length; // calculating the length of array
for (int i = 0; i < len-1; i++) {
// for optimization when array is already sorted & no swapping happens
boolean swapped = false;
for (int j = 0; j < len - i - 1; j++)
{
if (a[j] > a[j + 1]) //comparing the pair of elements
{
// swapping a[j+1] and a[i]
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
// swapping happened so change to true
swapped = true;
}
}
// if no swaps happened in any of the iteration
// array has become sorted so stop with the passes
if(swapped == false)
break;
}
}
/* Prints the array */
static void printArray(int a[])
{
int len = a.length;
for (int i = 0; i < len; i++)
System.out.print(a[i] + " "); //printing the sorted array
System.out.println();
}
// Main method to test above
public static void main(String args[])
{
int arr[] = {1, 2, 3, 4, 5, 6, 7};
bubbleSort(arr);//calling the bubbleSort function
System.out.println("Sorted array");
printArray(arr); //calling the printArray function
}
}
Advantages of using Bubble Sort
LOL !!!! None, but if you still have to know then they could be –
Bubble sort would need lesser memory then other sorting techniques.
Even Noob Programmers can understand it
Why Bubble sort Sucks !!!
Its, time complexity is O(n2), which is shit
When you have very large items then, it sucks even more as it becomes even more slow thanks to O(n2)
The algorithm will be slowest when the array is sorted by in reverse
Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.
public class Main
{
public static void main(String[] args)
{
int a[]={7,9,3,0,2,1,5};
for(int i=0; i<a.length-1; i++){
for(int j=0; ja[j+1]){
//bubble sort
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(int i=0; i<a.length; i++){
System.out.print(a[i]+" ");
}
}
}
public class Main
{
public static void main(String[] args)
{
int a[]={8,7,6,5,4,3,2,1};
for(int i=0; i<a.length-1; i++){
for(int j=0; ja[j+1]){
//bubble sort
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(int i=0; i<a.length; i++){
System.out.print(a[i]+" ");
}
}
}
what is the time complexity of bubble sort for all case ?
https://prepinsta.com/cpp-program/bubble-sort/ visit this page Ritik. We hope this will resolve your queries