Array Sorting Algorithms: Bubble Sort and its efficiency

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.

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.

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

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

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

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

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

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

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

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

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 < a; b++) {
         if(arr[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.

Ex, for an array of 10000 elements

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.