How to implement bubble sort by using only one for loop

In this tutorial we are going to learn about implementing the bubble sort using only one for loop.

Bubble sort simply swaps adjacent items if the two it is looking at are incorrectly ordered. It continues moving down the list, and will keep on going until everything is sorted.

Bubble sort is iterative algorithm. Also analysis is based on simple summation. There is no reason to avoid for loop. If you really have to any other loop supported by syntax should do (goto statement is also valid, check this example). Here is analysis (a simple summation of steps) 1+2+3+…+(n−1)=n(n−1)/2, O(n(n−1)/2) = n2

public class BubbleSort {
	public static void main(String args[]) {
		int[] arr = new int[] { 5,32,9,1,6,4,10,3,7,8};
		int N = arr.length, count = N * (N - 1) / 2, last = N - 1;
		int i = 0, j = 1;
		for (int i1 = 0; i1 < count; i1++) {
			if (j == last + 1) {
				last--;
				i = 0;
				j = 1;
			}
			if (arr[i] > arr[j])
				swap(arr, i, j);
			i++;
			j++;
		}
		for(int x=0;x<=N-1;x++)
		{
			System.out.println(arr[x]);
		}
	}

	private static void swap(int[] arr, int i, int j) {
		// TODO Auto-generated method stub
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}

If any algorithm’s runtime complexity depends upon the initial ordering of the input sequence or in other words We can say if an algorithm gets the benefit of initial order of the input, is called adaptive algorithm.

Now, in case of bubble sort technique, we just compare the adjacent elements to keep them in correct order(by swapping, if in wrong order), and we check again and again to until we find no any swaps between any 2 adjacent elements in the sequence. If there is no any swaps then we can surely say that sequence is sorted.

So, now think, if an array is already sorted,

let’s say A = [3, 5, 7, 9, 10, 13, 15]

then we do require only 1 pass through the array and we will find that they all are in correct order(means no swaps occurred), hence list is sorted.

In this case it is linear time i.e., O(n).

Again think, if an array is reverse sorted, let’s say A = [15,13, 10, 9, 7, 5, 3]

then we do require (n-1) passes through the array and then we will find that they all are in correct order(means no swaps occurred), hence list is sorted after traversing list n-1 time.

In this case time is O(n∗(n−1)) ~ O(n2).

Hence, we saw that time complexity of bubble sort strongly depends upon the initial order of the sequence, due to which this algorithm is adaptive.

Note: Naturally, bubble sort doesn’t include checking of swaps in a pass, this is what we have to keep track of if any swaps occurred or not. Means bubble sort is not naturally adaptable, rather it needs to be made adaptive.