BubbleSort with Java

Bubble sort is one of the easiest algorithms. It simply uses iteration and swapping in it. In this algorithm smaller elements of the array or list  bubbles up to first that’s why it’s named as bubble sort.

Say we have array of {5, 4, 0, 3, 7}, than bubble sort takes first element check whether it’s greater than second element and if it is greater than second one it swaps and keeps doing it for last element. So, we will have {4, 0, 3, 5, 7} after first pass.You can see that it’s still not sorted.We have to again do the same steps for element 4.

After doing this until any iteration does not need any swapping we can stop and we will have sorted array. Consider following steps,

PASS 1 : Take First Element
			5 4 0 3 7 : 5 > 4 : YES : SWAP
			4 5 0 3 7 : 5 > 0 : YES : SWAP
			4 0 5 3 7 : 5 > 3 : YES : SWAP
			4 0 3 5 7 : 5 > 7 : NO  : NO MORE ELEMENTS

PASS 2 : Take Second Element
			4 0 3 5 7 : 4 > 0 : YES : SWAP
			0 4 3 5 7 : 4 > 3 : YES : SWAP
			0 3 4 5 7 : 4 > 5 : NO  : MOVE AHEAD
			0 3 4 5 7 : 4 > 7 : NO  : NO MORE ELEMENTS

PASS 3 : Take Third Element
			0 3 4 5 7 : 0 > 3 : NO  : MOVE AHEAD
			0 3 4 5 7 : 0 > 4 : NO  : MOVE AHEAD
			0 3 4 5 7 : 0 > 5 : NO  : MOVE AHEAD
			0 3 4 5 7 : 0 > 7 : NO  : NO MORE ELEMENTS
		  
NO SWAPS. DONE!

As you can see we have to pass through or traverse 3 times for array of 4 elements.So, ultimately for worst case we need to pass through array for (n – 1) times if we have array of length n. Understand it with simple example,for array {2,1} we need to pass it through 1 times to sort this array.

Let’s consider following implementation in Java,

public class BubbleSort {

	public static void simpleBubbleSort(int[] arr) {
		int temp = 0;
		int pass = arr.length - 1;
		
		System.out.println("Unsorted 	: "+ Arrays.toString(arr));
		
		while(pass != 0) {
			for(int i = 0; i < arr.length - 1; i++) { 
                if(arr[i] > arr[i + 1]) {
					temp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = temp;
				}
			}
			pass --;
		}
		
		System.out.println("Sorted 		: " + Arrays.toString(arr));
	}
	
	public static void main(String[] args) {
		int arr[] = new int[]{9,6,2,5,3};
		simpleBubbleSort(arr);
	}

}

We have to check for every element for (n-1) times. Worth to note that worst case time complexity of bubble sort is O(n2). But here we can definitely improve this implementation, check following points,

  • In bubble sort after first pass element reaches to it’s exact place. i.e. {5,4,2,6} after first pass we will have {4,2,5,6}, so ultimately we now only need to check for element 4 for (n – 1) elements of array because one element 5 is already placed properly.
  • Apart from the worst case, we can simply break if we don’t need to swap any element in any pass with the help of counter or flag.

So, this is the implementation of bubble sort which is now quite optimized than the previous one.

public class BubbleSort {

	public static void optimizedBubbleSort(int[] arr) {
		int temp = 0;
		int passThrough = arr.length - 1;
		boolean isNoSwaps = false;
		
		System.out.println("Unsorted 	: "+ Arrays.toString(arr));
		
		while(passThrough!= 0) {
			isNoSwaps = true;
			for(int i = 0; i < passThrough; i++) {
                if(arr[i] > arr[i + 1]) {
					temp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = temp;
					isNoSwaps = false;
				}
			}
			passThrough --;
			
			if(isNoSwaps) {
				break;
			}
		}
		
		System.out.println("Sorted 		: " + Arrays.toString(arr));
	}
	
	public static void main(String[] args) {
		int arr[] = new int[]{9,6,2,5,3};
		optimizedBubbleSort(arr);
	}

}

Note that in both the cases we will have following output,

Unsorted 	: [9, 6, 2, 5, 3]
Sorted 		: [2, 3, 5, 6, 9]

You can use outer for loop as well instead of while loop, it’s just matter of taste. But note that time complexity is high for this algorithm. Moreover, it’s inefficient if we want to sort large number of collection or array. Average time increases exponentially and so not quite efficient for real life applications. Specifically it’s too slow compared to other sorting algorithms.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s