Bubble Sort with Java

Usually, the first sort algorithm many developers learn is the Bubble sort. That’s because it’s the easiest sort algorithm to implement. The performance is not good but it does the job.

The basic idea of the bubble sort is to iterate over the array, iterate again and compare every element. If the element from the first looping is lower than the other looping element, then swap the elements. By doing that to the end of the array the Bubble sort will be done.

Let’s see how is that in a diagram:

As you can see in the diagram above almost all elements will be compared and that’s why it’s so inefficient in terms of performance.

Now let’s see how to implement the Bubble sort in Java:

public class BubbleSort {

    public static void main(String[] args) {
        int[] array = {2, 9, 5, 5, 6, 8, 10};
        int[] result = sortOptimized(array);
        Arrays.stream(result).forEach(e -> System.out.print(e + " "));
    }

    public static int[] sort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] > array[j]) {
                    swapElements(array, i, j);
                }
            }
        }

        return array;
    }

    private static void swapElements(int[] array, int i, int j) {
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}

Output:
2 5 5 6 8 9 10

Code analysis:

The code above will create the first looping with the index i and then iterate through another looping with the index of j. Notice that j starts with i + 1 to avoid a redundant comparison between i and j as index 0.

Then every element from i will be compared with the elements from the other array iteration using the index of j. When all elements are compared and sorted the Bubble sort will be done.

Optimized Bubble Sort

Notice that there is the possibility in the algorithm above that the whole array is already sorted. But if that happens in the code above we will iterate through the array anyway. We don’t have any way to control that via code.

However, in the following code, we will see a way to prevent iterating through the array multiple times if the array is already sorted. Let’s see how that works:

public class BubbleSort {

  // Omitted the above code
  public static int[] sortOptimized(int[] array) {
    var isSorted = false;
    var counter = 0;

    while (!isSorted) {
      isSorted = true;
      for (int i = 0; i < array.length - 1 - counter; i++) { 
        if (array[i] > array[i + 1]) {
          swapElements(array, i, i + 1);
          isSorted = false;
        }
      }

      counter++;
    }

    return array;
  }
  // Omitted swapElements method

}

Code analysis:

To start if we compare the number of iterations between the non-optimized Bubble sort and the optimized Bubble sort the difference is huge depending on the input array. Using the array from the code examples, in the non-optimized Bubble sort, we do 21 iterations while in the optimized Bubble sort we do 11 iterations.

The code difference is that instead of comparing every element no matter what, we have the isSorted flag. Also, we will sort the previous element with the next element and iterate over the whole array how many times is necessary until it’s fully sorted.

If an array of 7 elements is already sorted, there will be only 7 iterations using the optimized Bubble sort. On the other hand, using the non-optimized Bubble sort algorithm we will have 21 iterations.

Therefore, when implementing the Bubble sort algorithm, remember to implement the optimized algorithm to enhance performance!

Big (O) Notation Complexity

Time Complexity: Since we have two loopings and we compare every element in the array, the performance is not good. It has exponential complexity. The time complexity is O(n^2) which translates to (number of elements of the array * number of elements of the array). Also, keep in mind that this number doesn’t need to be very precise, it’s a rough estimation instead.

In our code example using an unsorted array of 7 elements, we iterate over the inner array 21 times, if we count both it’s 28 iterations using the non-optimized algorithm. Even still, it’s not 49 (the result of 7 * 7) as it should be with the Big(O) notation estimation. It’s close enough though.

Space Complexity: We only swap elements in the array in place. Therefore, since we don’t use any auxiliary array the space complexity is O(1).

Summary

The Bubble sort algorithm is the simplest sorting algorithm to implement and it’s a good one to get started. The performance is not good as well. Let’s see the key points of this algorithm:

• It’s the simplest sort algorithm.
• It will iterate over all elements with the non-optimized algorithm
• It will have a significant gain in performance by using the optimized Bubble sort algorithm
• It will have two loopings so that the comparison between elements is possible.
• The second array iteration will start always with i + 1 to avoid redundant comparison