Sorting Algorithm - Bubble Sort

Given an array, sort the array using Bubble Sort algorithm.


Question Asked in

Goldman Sachs


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




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


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




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)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer