- 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
- Given an unsorted array of length n.
- Start iterating through the array
- 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.
- If current element is larger than next element
- 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
S. No. | Cases | Complexity |
---|---|---|
1 | Best case | O(n^2) |
2 | Average case | O(n^2) |
3 | Worst case | O(n^2) |
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] |