Bubble Sort in Java

Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them if they are in the wrong order that’s expected. Bubble sort algorithm is not suitable for large data sets as its average and worst-case time complexity are quite high.

Algorithm for Bubble Sort in Java

1) Start with the first element of the array.
2) Compare the current element with the next element.
3) If the current element is greater than the next element, swap them.
4) Move to the next element and repeat steps 2 and 3 until the end of the array.
5) Repeat steps 1-4 until no more swaps are needed, indicating the array is sorted.

Bubble Sort Algorithm Syntax

bubbleSort(array)
  for i <- 1 to (sizeOfArray - 1)
    for j <- 1 to (sizeOfArray - 1) - i
      if leftElement > rightElement
        swap leftElement and rightElement
end bubbleSort

Optimized Bubble Sort Algorithm

In Bubble Sort algorithm all the comparisons are made even if the array is already sorted which increases the execution time. To solve this an extra variable swapped is brought in. The value of swapped is set true if there occurs swapping of elements. Otherwise, it is set false.

After an iteration, if there is no swapping, the value of swapped will be false which means elements are already sorted and there is no further iterations is required. This reduces the execution time and helps to optimize the bubble sort.

Algorithm for optimized bubble sort (Syntax)

bubbleSort(array)
  for i <- 1 to (sizeOfArray - 1)
    swapped <- false
    for j <- 1 to (sizeOfArray - 1) - i
      if leftElement > rightElement
        swap leftElement and rightElement
        swapped <- true
    if swapped == false
      break
end bubbleSort

Bubble Sort Complexity:

Time Complexity: O(n2)

Bubble Sort has a time complexity of O(n2) in the worst and average cases, where n is the number of elements in the array. In the worst case, for each element in the array, we may need to compare it with every other element and so Bubble Sort is not suitable for large datasets due to its poor time complexity.

Space Space: O(1)

Space complexity is O(1) because an extra variable is used for swapping.In the optimized bubble sort algorithm, two extra variables are used. Hence, the space complexity will be O(2).

Advantages of Bubble Sort:

1) Bubble sort is easy to understand and implement.
2) It does not require any additional memory space to sort an array.
3) Since it is a stable sorting algorithm, elements with the same key value maintain their relative order in the sorted output.

Disadvantages of Bubble Sort:

1) Bubble sort has a time complexity of O(n2) which makes it very slow for large data sets.
2) Bubble sort is a comparison-based sorting algorithm, that requires a comparison operator to determine the relative order of elements in the input data set. It can limit the efficiency of the algorithm in certain cases.
3) It can limit the efficiency of the algorithm in certain cases.

Program 1 : Bubble sort in Java (Without Optimization)

import java.util.Arrays;

public class BubbleSortProg {

	static void bubbleSortMethod(int array[]) {
	    int size = array.length;
	    
	    for (int i = 0; i < (size - 1); i++)
	    
	      for (int j = 0; j < (size - i - 1); j++)

	        if (array[j] > array[j + 1]) {

	          int temp = array[j];
	          array[j] = array[j + 1];
	          array[j + 1] = temp;
	        }
	  }

	  public static void main(String args[]) {
	      
	    int[] dataList = { -8, 52, 24, 0, -19 };
	    
	    bubbleSortMethod(dataList);
	    
	    System.out.println("Sorted Array in Ascending Order Using Bubble Sort : ");
	    System.out.println(Arrays.toString(dataList));
	  }
}
Output :

Sorted Array in Ascending Order Using Bubble Sort : 
[-19, -8, 0, 24, 52]

Program 2 : Optimized Bubble Sort in Java Using swapped variable

import java.util.Arrays;

public class BubbleSortOptimized {

	static void bubbleSortMethodOptimized(int array[]) {
	    int size = array.length;
	    
	    for (int i = 0; i < (size-1); i++) {
	    
	      boolean swapped = false;
	      
	      for (int j = 0; j < (size-i-1); j++) {

	        if (array[j] > array[j + 1]) {

	          int temp = array[j];
	          array[j] = array[j + 1];
	          array[j + 1] = temp;
	          
	          swapped = true;
	        }
	      }
	      if (!swapped)
	        break;

	    }
	  }

	  public static void main(String args[]) {
	      
		int[] dataList = { -8, 52, 24, 0, -19 };
	    
	    bubbleSortMethodOptimized(dataList);
	    
	    System.out.println("Sorted Array in Ascending Order:");
	    System.out.println(Arrays.toString(dataList));
	  }
}
Output :

Sorted Array in Ascending Order:
[-19, -8, 0, 24, 52]
Scroll to Top