Sort integer array using bubble sort algorithm in java (example)

• Given an unsorted array in java.
• Sort the given input array using bubble sort algorithm.
• Bubble sort is a sorting technique used to sort the elements of list data structure.

Algorithm to sort given input array using bubble sort

1. Given an unsorted array of length n.
2. Start iterating through the array
3. There will be two loops to sort array using bubble sort algorithm.
   • Outer loop iterate from 0 to n – 1, Let outerindex be its index.
   • Inner loop will iterate from 0 to n – outerIndex – 1, Let innerindex be its index.
   • Compare the adjacent elements of array
     • If current element is larger than next element
       • Then swap element, so that elements are in sorted order
     • Else, no need to do anything, as elements are already sorted.
4. Once we are out of loops, we will get sorted array.

Example – sort integer array using bubble sort algorithm in java

• Let us take an example to understand the sorting algorithm (step by step iteration).
• Given an unsorted array {10,7.25,20,12,9}.

• Start iterating through the array of length 6
  • Let iterate through outer loop from 0 to 5 (i.e. outerindex)
  • Start one more iteration, which will actually sort the array.
    • Let it be innerIndex and iterate from 0 to n – outerIndex – 1
    • Compare the adjacent elements of an array
    • Compare element 10 and 7
      • 10 > 7 ? yes, swap the elements [Ref Fig 2]

• While going through iteration compare second pair of elements
  • Check 10 > 25 ?
  • Its false, so swapping is not required as its already sorted [Ref Fig 3]

• Compare Third pair of elements
  • Check 25 > 20 ?, Its true
  • Let us swap these elements, as these are not sorted [Refer Fig 4]

• Compare fourth pair of elements
  • Check 25 > 12 ?, Its true
  • Let us swap these elements as these are not sorted [Refer Fig 5]

• Compare fifth or last pair of elements
  • Check 25 > 9 ?, Its true
  • Let us swap these elements as these are not sorted [Refer Fig 6]

• After completion of inner loop, we will get final position of 25.
  • Now, we have concentrate of rest of five elements 0 to 4
• After every iteration, each element will reach to its final position [Refer Fig 7]
  • At last, we will get the sorted elements

Why it is called bubble sort ?

• Bubble always tends to reach to the surface, which is its best place.
  • Similarly in bubble sort algorithm, element(s) tends to move to its right position, after every iteration.
• If we look at the Fig 7, we can see the after every iteration elements tends to move to their appropriate positions.

Complexity of bubble sort algorithm

Program – Sort array using bubble sort algorithm in java

private static void bubbleSort(int[] arr) {
		for (int outterIndex = 0; outterIndex < arr.length; outterIndex++) {
			for (int innerIndex = 0; innerIndex < arr.length - outterIndex - 1; innerIndex++) {

				if (arr[innerIndex] > arr[innerIndex + 1]) {
					swap(arr, innerIndex);
				}
			}
		}
		System.out.println(Arrays.toString(arr));
	}

• We have seen the complexity analysis of bubble sort its (n^2),
  • We can improve it further i.e. If we have sorted the array, we do not need to further apply the bubble sort on it.
• We will use a flag (isSwapHappened )to keep track of sorting.
• Let us go through the code to understand our reasoning.

	private static void improvedBubbleSort(int[] arr) {
		boolean isSwapHappened = false;
		for (int outterIndex = 0; outterIndex < arr.length; outterIndex++) {
			isSwapHappened = false;
			for (int innerIndex = 0; innerIndex < arr.length - outterIndex - 1; innerIndex++) {

				if (arr[innerIndex] > arr[innerIndex + 1]) {
					swap(arr, innerIndex);
					isSwapHappened = true;
				}
			}
			if (isSwapHappened == false) {
				// Now array is sorted, no need to swap now
				System.out.println("No swap happened for current iteration");
				break;
			}
		}
		System.out.println(Arrays.toString(arr));
	}

Program – sort given array using bubble sort algorithm in java 

package org.learn.arrays;

import java.util.Arrays;

public class BubbleSort {

	public static void main(String[] args) {
		int[] arr = { 10, 7, 25, 20, 12, 9 };
		System.out.println("Input array : " + Arrays.toString(arr));
		System.out.println("Sorting using bubble sort :");
		bubbleSort(arr);
		System.out.println("Sorting using improved Bubble sort :");
		// Take an example of partially sorted array
		int[] partiallySortedArray = { 25, 20, 12, 7, 9, 10 };
		improvedBubbleSort(partiallySortedArray);
	}

	private static void bubbleSort(int[] arr) {
		for (int outterIndex = 0; outterIndex < arr.length; outterIndex++) {
			for (int innerIndex = 0; innerIndex < arr.length - outterIndex - 1; innerIndex++) {

				if (arr[innerIndex] > arr[innerIndex + 1]) {
					swap(arr, innerIndex);
				}
			}
		}
		System.out.println(Arrays.toString(arr));
	}

	private static void improvedBubbleSort(int[] arr) {
		boolean isSwapHappened = false;
		for (int outterIndex = 0; outterIndex < arr.length; outterIndex++) {
			isSwapHappened = false;
			for (int innerIndex = 0; innerIndex < arr.length - outterIndex - 1; innerIndex++) {

				if (arr[innerIndex] > arr[innerIndex + 1]) {
					swap(arr, innerIndex);
					isSwapHappened = true;
				}
			}
			if (isSwapHappened == false) {
				// Now array is sorted, no need to swap now
				System.out.println("No swap happened for current iteration");
				break;
			}
		}
		System.out.println(Arrays.toString(arr));
	}

	private static void swap(int[] arr, int index) {
		int temp = arr[index];
		arr[index] = arr[index + 1];
		arr[index + 1] = temp;
	}
}

Output – sort array using bubble sort algorithm in java

Input array : [10, 7, 25, 20, 12, 9]
Sorting using bubble sort :
[7, 9, 10, 12, 20, 25]
Sorting using improved Bubble sort :
No swap happened for current iteration
[7, 9, 10, 12, 20, 25]