Bubble Sort in Java

Here we will discuss the most simplest sorting algorithm Bubble Sort which works repeatedly swapping of the adjacent elements if they are in wrong order.

The logic in Bubble Sort is to sort the elements pass by pass.
In each pass the elements are placed in its perfect positions starting from the last i.e the largest element is placed as the last element in the list in the 1st pass. Similarly, the second largest element is placed as the second last element in the element in 2nd pass, and so on.




As you can see (above fig.) in each pass higher elements are getting sorted first and elements looks like bubbling for one place to other, hence the name Bubble Sort.

Lets gets hands on with the algorithm by writing a Java code.

import java.util.Arrays;


public class BubbleSort {

 public static void main(String[] args) {
  int [] array = {5,2,1,7,4,9};
        System.out.println(Arrays.toString(array));
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
        
 }
 private static int[] bubbleSort(int[] array) {
  for(int i = 0; i < array.length -1 ; i++){
   for(int j = 0; j < array.length - (1+i) ; j++){
    if(array[j] > array[j+1]){
     int temp = array[j+1];
     array[j+1] = array[j];
     array[j] = temp;
    }
   } 
  }
  return array;
 }

}
//output
//[5, 2, 1, 7, 4, 9]
//[1, 2, 4, 5, 7, 9]

Here sorting is for descending order. As you can see we have two loops.
One for loop is for the pass. The other for loop compares each adjacent element starting from the 0th position and swap whenever it's

array[j] > array[j+1]

So in each pass we are putting the higher elements one by one in the last.
with each pass the number of comparisons also decreases as you can see from the line

j < array.length - (1+i) 

i is incrementing thereby the traversal in second loop decrease by 1 in each pass. This is obvious because we have already placed the right elements in previous passes so no need to compare those elements.

Analysis of Bubble Sort

• Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.
• Best Case Time Complexity: O(n). Best case occurs when array is already sorted.
• Auxiliary Space: O(1)
• Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already sorted.
• Sorting In Place: Yes
• Stable: Yes

Hope you like it. Stay tune as we will discuss and explain other interesting sorting algorithms in coming tutorial. Please comments for any doubts.

Happy Learning !!!

SHARE

Onlinecodegeek