Bubble Sort

Bubble sort is the most easy sorting algorithm in which we compare adjacent elements and swap them depending to our conditions.

suppose our array is int arr[]= {10,8,9,5,7,6,3,0,1,-3,-6,-9}; 

 we want to sort the array in ascending order then  after sorting the array would look like {-9 ,-6 ,-3, 0, 1 ,3 ,5, 6, 7, 8 ,9, 10 };

We will use Bubble Sort of 3 level

Algorithm:

1. We run two loops the outer loop will be for iterating on the array and the inner loop will perform the comparison and  swapping part.
2. If the next element is smaller than the current element than we swap it with current element.

 

Working of Bubble Sort:

lets take array as

arr = [5, 3, 4, 2, 1]

If we plot the array it look like this

Now to understand the working properly consider this elements as students with the respective height in units.

Iteration 1:

• In first iteration student 1 asks student 2 that Am i greater than you? He says yes, So they swap their position.arr=[3,5,4,2,1]
• Now student with height 5 asks student with height 4 Am i greater than you ? He says yes! So they swap their position. arr[3,4,5,2,1]
• Again 5 asks 2 , and 5>2 , so they swap . arr[3,4,2,5,1]
• 5>1 so They swap position. arr=[3,4,2,1,5]
  

Thus after First Iteration the array becomes arr=[3,4,2,1,5]

 

Iteration 2:

 

• The array is now [3,4,2,1,5], similarly 3 asks 4 Am i greater?He says No.So they don't swap their position.
• 4>2 , yes, so they swap their position.
• Similarly after repeating the same condition, the next highest height student come to its right position.

 

 

Iteration 3:

 

 

 

 

Iteration 4:

 

Its that simple algorithm, but we use bubble sort of 3 different levels to reduce the time required to sort the array

In every iteration the largest number is positioned at its appropriate  end position. 

1.Level 1

public int bubbleSortLevel1(int[] arr) {

int total_iterations=0;

for(int i=0;i<arr.length;i++)

{

for(int j=0;j<arr.length-1;j++)

{

if(arr[j]>arr[j+1])

{

int temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

}

total_iterations++;

}

System.out.print("i="+i+" : ");

print(arr);

}

return total_iterations;

}

Output: 

You can see that we require 132 Iterations for sorting the Array

2.Level 2

In this level we add outer loop iterator in the condition of for loop , because you can see that after every iterations the highest number is positioned to its appropriate end position, thus to avoid extra comparisons we reduce the number of iterations of inner loop.

public int bubbleSortLevel2(int[] arr) {

int total_iterations=0;

for(int i=0;i<arr.length;i++)

{

for(int j=0;j<arr.length-i-1;j++)

{

if(arr[j]>arr[j+1])

{

int temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

}

total_iterations++;

}

System.out.print("i="+i+" : ");

print(arr);

}

return total_iterations;

}

In this level we added a "i" variable in the inner loop to reduce

 the number of iterations

 

Output:

 

You can see now the iterations are decreased to 66 , thus if the search space  is huge enough it will be a good decrement in the time consumption.

 

3.Level 3

In this level we use a flag variable to avoid extra comparison if the array is already sorted .

public int bubbleSortLevel3(int[] arr) {

int total_iterations=0;

for(int i=0;i<arr.length;i++)

{

boolean flag=true;

for(int j=0;j<arr.length-i-1;j++)

{

if(arr[j]>arr[j+1])

{

flag=false;

int temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

}

total_iterations++;

}

if(flag) {

break;

}

System.out.print("i="+i+" : ");

print(arr);

}

return total_iterations;

}

Output:

   
 

Comparing Level 2 and Level 3 Bubble Sort:

Lets see it with comparing level 2 and level 3 bubble sort

We will use int arr2[]= {-9 ,-6 ,-3, 0, 1 ,3 ,5, 6, 7, 8 ,9, 10 }; as the array is already sorted so their is no need for extra computation 

So lets check our both level codes

Level 2 Bubble Sort:

 

You can see that even if  no computation is needed it still does 66 iterations for i value ranging from 0 to 11

 

Level 3 Bubble Sort:

You can see that here only 11 comparison is done and only i=0 is run because the array is sorted  Thus the time is reduced to run the program.

 

 

Related Posts:

 

Bubble Sort In Python 

 

Conclusion:

 

Thus we can use any Sorting level for sorting if the search space that is the array in this case is small.But if the space is large enough then it is good to use level2 or level 3 sorting technique