Bubble Sort Algorithm

by

In this article, we would try to understand bubble sorting algorithm in more detail. This is the primitive or the easiest sorting algorithm available in the lot which sorts an array by repeatedly swapping two adjacent elements until the whole array is sorted.

We loop through the whole array and check for the two adjacent elements. If we find the left element to be bigger than the right element, we swap them. So, the algorithm works by placing the largest element at the last index in the first iteration. In the second iteration, the second highest element is placed in the second last index. This goes on till the array is sorted and there are no swaps remaining. Let’s look at the steps of the algorithm.

Algorithm

1. Start

2. The array being arr, we have two more loop variables i and j, both starting from 1.

3. Now, till i reach arr.length which is the size of the array, we loop using j, which will go till arr.length -   i.

4. If arr[j] < arr[j-1], we swap the values. 

5. Increment both i and j. Goto step 3.

6. Exit

Bubble Sort Code in Java

public static void bubbleSort(int[] arr) {
		
	for(int i=1; i <= arr.length; i++) {
		boolean swap = false;
		for(int j=1; j <= arr.length - i; j++) {
			if(arr[j] < arr[j-1]) {
				int temp = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = temp;
				swap = true;
			}
		}
		if(!swap) {
			break;
		}
	}
	System.out.println(Arrays.toString(arr));
}

The above method implements bubble sort. We expect this method to take in an integer array, sort it and then print the sorted array output. We need to call the bubbleSort method from a main method to implement bubble sort.

Time Complexity

The time complexity is considered asymptotically and this O(n^2). The space complexity is O(1). Your can read more about it here. Due to it’s inefficient time complexity, bubble sort is not recommended to be used in case of arrays having large number of array elements.
However, it is an stable sorting algorithm, which means that the original sequence of the array elements in intact and it suitable for smaller number of array elements.

Leave a Comment