Java Bubble Sort Example

Bubble Sort is one of the basic sorting algorithm , it compares adjacent elements and exchange which ever element is heavier . Bubble Sort is also referred as sink sort .

Bubble sort places the lighter element up and greater element down the array using iterations and passes .

Bubble Sort Logic

Bubble sort logic Start’s from the start of the array and start swapping adjacent elements . Swap only if you need to push lighter elements up else leave the adjacent pair . You can enhance sorting logic bit more but this is basic logic . Once you start comparing adjacent elements after N passes and N iterations you will have a sorted array .

Repeat the operation n times where n is the length of array .

Pseudo code for Bubble Sort using Java

int pass,j,inpArr[200],temp;

for(pass=0; pass<n; pass++) {
for(j=0; j<n-1; j++) {
  if(inpArr[j] > inpArr[j+1]) {
    temp = arrNum[j+1];
    inpArr[j+1] = inpArr[j];
    inpArr[j] = temp;
}
}
}

Code Explanation

• In the above code inpArr[100] is input array which needs to be sorted n is number of elements in array
• We will be running comparison for N number of passes and in each pass we compare the adjacent elements n times
• In Each pass we compare adjacent element and move heavier elements down and lighter element up.

Lets take an example of the array [3.12,-5,-6,72,21,-7,45] , Have a look at the code how it performs in Pass 1 and Pass2 .

In Pass 1 , All adjacent elements are compared and moved accrodingly , lets have alook at pass2

If you have seen till the 2nd pass we have all the elements sorted .

Time Complexity Of Bubble Sort

As you have seen we compare elements in each pass and no of pass is same as no of elements N , adding up all passes below

1+2+3+4+5…+(N-1) = N*(N-1)/2

So we are iterating the array every time hence the best case and worst case would be same as we do it in every scenario.

What if we want to decrease the complexity to N-1 comparisons ?

Let me know in comments if You can do it ?

Java Code for Bubble Sort

Here is the corresponding java code ,

package org.frugalisminds;

import java.util.Arrays;

public class BubbleSort {
	int[] bubbleSort(int[] inpArr) {
		int num = inpArr.length;
		for (int pass = 0; pass < num - 1; pass++) {
			for (int j = 0; j < num - pass - 1; j++) {
				if (inpArr[j] > inpArr[j + 1]) {
					int temp = inpArr[j];
					inpArr[j] = inpArr[j + 1];
					inpArr[j + 1] = temp;
				}
			}
		}
		return arrNum;
	}

	public static void main(String[] args) {
		BubbleSort bs = new BubbleSort();
		int[] arrSortFrugalis = { 3,12,-5,-6,72,21,-7,45 };
		System.out.println("After sorting array -: " + Arrays.toString(bs.bubbleSort(arrSortFrugalis )));

	}
}

Output :- After sorting array -: [-7, -6, -5, 3, 12, 21, 45, 72]

Have a look at one of Binary Search bug as Well.