Bubble Sort Algorithm: Java Implementation - KodeSrc.

Bubble Sort In Java

Bubble Sort is a foundational algorithm in computer science, known for its simple concept and easy implementation. It works by comparing adjacent elements in a list and swapping them if they’re out of order, gradually sorting the entire list. Although not the most efficient for large datasets, Bubble Sort is perfect for understanding basic sorting techniques. In this article, we’ll break down the steps of Bubble Sort, explore its implementation in Java , and analyze its performance to help you master this essential algorithm. Let's get started!

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

 If we were to sort the array in ascending order, it would appear something like this: {-9,-6,-3, 0, 1,,3,5, 6, 7, 8,,9, 10 };

We will use Bubble Sort of 3 level

Algorithm:

•   We do two cycles. The inner loop will carry out the comparison and switching operations, while the outside loop will iterate across the array.
•  We exchange the current element with the next if it is smaller than the 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:

• Student 1 asks Student 2 in the first repetition, "Am I greater than you?" Yes, he responds, and they switch places.[3,5,4,2,1] is arr.
• Student who is 5 feet tall now asks student who is 4 feet tall. Do I surpass you in any way? He affirms. Thus, they exchange places. [3,4,5,2,1] arr.
• Once more, 5 asks 2, and since 5>2, they switch. [3,4,2,5,1] arr.
• 5>1, therefore they switch places. [3,4,2,1,5] is arr.
  

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

 

Iteration 2:

 

• At this point, the array is [3,4,2,1,5]. Likewise, 3 queries 4: Am I greater?No, he replies.Consequently, they don't move places.
• 4>2? yeah, They switch positions.
• The next tallest student reaches its proper position after repeating the same requirement.
  

 

 

Iteration 3:

 

 

 

 

Iteration 4:

 

This is a straightforward technique, but to cut down on the amount of time needed to sort the array, we employ three-level bubble sort.

The greatest integer is placed at the proper end location in each iteration.

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

We include an outer loop iterator in the for loop condition at this level because, as you can see, the highest integer is positioned at the proper end position after each iteration. As a result, we limit the number of inner loop iterations to prevent unnecessary comparisons.

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:

 

As you can see, there are now only 66 iterations, which should result in a significant reduction in the amount of time needed provided the search space is large enough.

 

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.

Conclusion:

Bubble Sort serves as an excellent introduction to sorting algorithms due to its simplicity and clear logic. Although it is not efficient for large datasets, its value lies in teaching the core concepts of comparisons and swaps in data organization. By implementing Bubble Sort in programming languages like Java and Python, you not only learn the mechanics of sorting but also develop a better understanding of algorithm design. This foundational knowledge sets the stage for mastering more advanced and efficient sorting techniques in the future.