Array Sorting Algorithms: Bubble Sort and its efficiency

Last updated : March 5, 2022

Sorting is a prerequisite for most search algorithms. Sorting can be time-consuming, and its efficiency relies heavily on the amount of data involved. Bubble sort, Selection sort, and Insertion sort are three simple algorithms for small amounts of data. But they are comparatively slow and inefficient when it comes to a large amount of data. Most sorting algorithms can only work with two elements at a time. They compare two elements and swap them if necessary.

In this chapter, we will take a look at the Bubble sort algorithm. We will also analyze its efficiency.

Bubble Sort Algorithm

Bubble sort is the simplest sorting algorithm in use. But it is slow and inefficient. Its efficiency is O(N²). It may only be suitable to sort small arrays.

In bubble sort, the sorting starts from the left (beginning) of the array and compares two elements at a time. In other words, the first comparison is element 0 and element 1. If the value in element 0 is larger than the value in element 1, swap them and move one position forward. This iteration continues until the end of the array. At the end of the first iteration, we have the largest value at the end of the array.

How Bubble Sort works

Now let's try to bubble sort the below array.

int arr = {3,10,8,9,7,5,4,6,2,1};

Array length is 10

We need 9 iterations = n

We need 45 comparisons (n(n+1)/2)

In the first iteration, first comparison, we compare element 0 with element 1, or arr[0] with arr[1]. Since 3 < 10, no swap is required.

Bubble Sort iteration 1
Figure 1 :First iteration, no swap required

In the second comparison, arr[1] is greater than arr[2] (10 > 8), and we swap the values.

Bubble Sort iteration 2
Figure 2 :Second iteration, swap 10 and 8

Third comparison, arr[2] is greater than arr[3] (10 > 9), and we swap the values.

Bubble Sort iteration 3
Figure 3 :Third iteration, swap 10 and 9

Fourth comparison, arr[3] is greater than arr[4] (10 > 7), and we swap the values.

Bubble Sort iteration 4
Figure 4 :Fourth iteration, swap 10 and 7

Fifth comparison, arr[4] is greater than arr[5] (10 > 5), and we swap the values.

Bubble Sort iteration 5
Figure 5 :Fifth iteration, swap 10 and 5

Sixth comparison, arr[5] is greater than arr[6] (10 > 4), and we swap the values.

Bubble Sort iteration 6
Figure 6 :Sixth iteration, swap 10 and 4

Seventh comparison, arr[6] is greater than arr[7] (10 > 6), and we swap the values.

Bubble Sort iteration 7
Figure 7 :Seventh iteration, swap 10 and 6

Eighth comparison, arr[7] is greater than arr[8] (10 > 2), and we swap the values.

Bubble Sort iteration 8
Figure 8 :Eighth iteration, swap 10 and 2

Ninth comparison, arr[8] is greater than arr[9] (10 > 1), and we swap the values.

Bubble Sort iteration 9
Figure 9 :Ninth iteration, swap 10 and 1

Now we have the largest number at the rightmost element of the array. There are eight iterations left to sort the remaining nine elements. Listed below is the complete code to bubble sort the array.

private static void BubbleSort(int[] arr) {
	int length = arr.length;
	int temp;
	for(int a=length-1; a>0; a--) {		
		for(int b=0; b arr[b+1]) {
				temp = arr[b];
				arr[b] = arr[b+1];
				arr[b+1] = temp;
			}
		}
	}
	System.out.println(Arrays.toString(arr));
}

The Efficiency of Bubble Sort

As we discussed above, we need 9 iterations to sort an array with 10 elements. The inner loop makes 9 comparisons on the first pass, 8 on the second, and so forth.

9+8+7+6+........+1 = 45 comparisons for 10 elements. When the number of elements is represented by n,

(n-1)+(n-2)+(n-3)+(n-4)+......+1 = n(n-1)/2 = n²-1/2 = 45 for 10 elements

We can ignore the -1 for larger n's.

n²/2

Ex, for an array of 10000 elements

10,000*10,000/2 = 50,000,000 comparisons.

In the worst case scenario (array is inversely sorted), a swap happens in every comparison. Since the constants are not accounted in Big O notation, we can assume that bubble sort runs in O(N²) time. For 10,000 elements, 10,000*10,000 = 100,000,000 comparisons. Thats slow.

L Raney
By: L Raney
Lance is a software engineer with over 15 years of experience in full-stack software development.
Read more...

Comments are disabled

No Comments