Sorting Algorithm - Bubble Sort

Algorithm/Insights

Bubble sort is an in-place comparison sort. Bubble sort algorithm compares each pair of adjacent elements and swaps them if they are in the wrong order. The pass through the array is repeated until no swaps are needed, which indicates that the array is sorted.

Example- Consider the array:
12, 35, 87, 26, 9, 28, 7

First iteration:
[12, 35], 87, 26, 9, 28, 7     12 < 35, no swapping required
12, [35, 87], 26, 9, 28, 7     35 < 87, no swapping required
12, 35, [87, 26], 9, 28, 7     87 > 26, swap
12, 35, 26, [87, 9], 28, 7     87 > 9, swap
12, 35, 26, 9, [87, 28], 7     87 > 28, swap
12, 35, 26, 9, 28, [87, 7]     87 > 7, swap
12, 35, 26, 9, 28, 7, 87
As we can see here, the largest element is shifted to the end of the array. So, in next iteration, we need swapping till 2nd last element.

Second Iteration:
[12, 35], 26, 9, 28, 7, 87    12 < 35 no swapping required
12, [35, 26], 9, 28, 7, 87    35 > 26, swap
12, 26, [35, 9], 28, 7, 87    35 > 9, swap
12, 26, 9, [35, 28], 7, 87    35 > 28, swap
12, 26, 9, 28, [35, 7], 87    35 > 7, swap
12, 26, 9, 28, 7, 35, 87

Proceeding this way, we get sorted array after n iterations
7, 9, 12, 26, 28, 35, 87

Optimization- Consider the array:
3, 25, 46, 58, 70, 76
The array is already sorted. So, there will be no swapping, since all elements are in order.
After any iteration, if there is no swapping required, then it means the array is already sorted.
So, we can terminate the execution right there.

Reference: https://en.wikipedia.org/wiki/Bubble_sort

Code Snippet

			
package com.ideserve.questions.saurabh;

import java.util.Arrays;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given an array, sort the array using Bubble Sort algorithm.
 *
 * @author Saurabh
 */
public class BubbleSort {

	public static void bubbleSort(int[] array) {
		if(array == null || array.length < 2) {
			return;
		}
		int n = array.length;
		boolean swapped = true;
		while(swapped) {
			swapped = false;
			for(int j = 1; j < n; j++) {
				if(array[j-1] > array[j]) {
					swap(array, j-1, j);
					swapped = true;
				}
			}
			n--;	// nth element placed at correct position, so next iteration needs to be done till n-1th element
		}
	}

	private static void swap(int[] array, int i, int j) {
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;		
	}

	public static void main(String[] args) {
		int[] array = {12, 35, 87, 26, 9, 28, 7}; 
		bubbleSort(array);
		System.out.println("Sorted array: " + Arrays.toString(array));
	}
}
		

Order of the Algorithm

Time Complexity is O(n^2) in worst and average cases. O(n) best case, when the array is already sorted.
Space Complexity is O(1)