Bubble sort algorithm

Bubble Sort is the simplest sorting algorithm, where array is traversed from first element to last element to repeatedly swap the adjacent elements if they are in wrong order.

It is much less efficient on large data sets than more advanced algorithms such as quicksort, heapsort, or merge sort.

Bubble sort is an in-place and stable sorting algorithm that takes constant O(1) auxiliary space. Bubble sort is used in computer graphics to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n).

Bubble sort Time Complexity

Simple Bubble sort always takes О(n2) time even if the array is already sorted, however an optimized Bubble sort can produce average and best case results by stopping the iteration if there is no swap in inner loop.

An Optimized Bubble sort takes maximum time О(n2), if elements are sorted in reverse order and it takes minimum time О(n) when elements are already sorted.

Worst case time complexity : О(n2)
Best case time complexity : O(n)
Average case time complexity : О(n2)


Optimized Bubble sort implementation in Java

Lets assume we have an array having (7, 2, 1, 6, 2, 5, 3, 4) integer elements, we will starts a loop from first element (i=0) to end of array (i=n).

An inner loop will start from second element (i=1) to end of array (i=n) to check of current element is less than element present at i-1, if so we will swap both elements,

If at any point there is no swap in inner loop, that means the array is sorted now and there is no need for further iterations.

2, 7, 1, 6, 2, 5, 3, 4, i=0, j=1
2, 1, 7, 6, 2, 5, 3, 4, i=0, j=2
2, 1, 6, 7, 2, 5, 3, 4, i=0, j=3
2, 1, 6, 2, 7, 5, 3, 4, i=0, j=4
2, 1, 6, 2, 5, 7, 3, 4, i=0, j=5
2, 1, 6, 2, 5, 3, 7, 4, i=0, j=6
2, 1, 6, 2, 5, 3, 4, 7, i=0, j=7
1, 2, 6, 2, 5, 3, 4, 7, i=1, j=1
1, 2, 6, 2, 5, 3, 4, 7, i=1, j=2
1, 2, 2, 6, 5, 3, 4, 7, i=1, j=3
1, 2, 2, 5, 6, 3, 4, 7, i=1, j=4
1, 2, 2, 5, 3, 6, 4, 7, i=1, j=5
1, 2, 2, 5, 3, 4, 6, 7, i=1, j=6
1, 2, 2, 5, 3, 4, 6, 7, i=1, j=7
1, 2, 2, 5, 3, 4, 6, 7, i=2, j=1
1, 2, 2, 5, 3, 4, 6, 7, i=2, j=2
1, 2, 2, 5, 3, 4, 6, 7, i=2, j=3
1, 2, 2, 3, 5, 4, 6, 7, i=2, j=4
1, 2, 2, 3, 4, 5, 6, 7, i=2, j=5
1, 2, 2, 3, 4, 5, 6, 7, i=2, j=6
1, 2, 2, 3, 4, 5, 6, 7, i=2, j=7
1, 2, 2, 3, 4, 5, 6, 7, i=3, j=1
1, 2, 2, 3, 4, 5, 6, 7, i=3, j=2
1, 2, 2, 3, 4, 5, 6, 7, i=3, j=3
1, 2, 2, 3, 4, 5, 6, 7, i=3, j=4
1, 2, 2, 3, 4, 5, 6, 7, i=3, j=5
1, 2, 2, 3, 4, 5, 6, 7, i=3, j=6
1, 2, 2, 3, 4, 5, 6, 7, i=3, j=7

package com.tb.arrays.sort;

import java.util.Arrays;
import java.util.stream.Collectors;

public class BubbleSort {
	static int[] input = { 7, 2, 1, 6, 2, 5, 3, 4 };

	private static void sort(int[] input, int n) {
		boolean swap;
		for (int i = 0; i < n; i++) {
			swap = false;
			for (int j = 1; j < n; j++) {
				if (input[j] < input[j - 1]) {
					int tmp = input[j];
					input[j] = input[j - 1];
					input[j - 1] = tmp;
					swap = true;
				}
			}
			if (!swap)
				break;
		}
	}

	private static String printArrays(int[] input) {
		return Arrays.stream(input).mapToObj(String::valueOf).collect(Collectors.joining(", "));

	}

	public static void main(String[] args) {
		System.out.println("Array before sort: " + printArrays(input));
		sort(input, input.length);
		System.out.println("Array after sort: " + printArrays(input));
	}
}
Output: Output of above code will be something like this.

Array before sort: 7, 2, 1, 6, 2, 5, 3, 4
Array after sort: 1, 2, 2, 3, 4, 5, 6, 7
In this article we have seen "What is Bubble sort?", Bubble sort time complexity, usage and how to implement Bubble sort in Java.