Bubble sort explained to a 6-year-old kid

You're a programmer, right? But do you rally think like programmers (or computer scientists) do?

When going for job interviews, you're likely to meet data structure and algorithm questions. This helps companies make sure they hire a systematic problem solver developer.

In this shot, I want you to learn more about one of the simplest sorting algorithms out there: bubble sort. How it works and how do we implement it with Java language.

The bubble sort in a nutshell

There we are: what is bubble sort?

Bubble sort is one type of sorting algorithms, and the simplest one, which is used to repeatedly compare adjacent items in a list and exchange them if they are in wrong order.

Let consider a list that need to be sorted in ascending order. To do this with bubble sort, we will start by comparing the first item of the list with the second one, if the first item is greater than the second, we swap both items, and then move on to compare the second and the third items, and so on. So, for a given list of size n, we need to repeat this process n - 1 times.

Note:

• bubble sort is also called comparison alogorithm
• In real life, we can observe bubble sort when people in a queue wanting to be standing in a high wise sorted manner swap their positions among themselves until everyone is standing based on increasing order of heights

Let's visualize an example of bubble sort so that you get it very well.

Bubble sort in practice

Here, I'll explain with an example how the bubble sort works, then after we will implement the algorithm in Java.

Let's consider this list of integer values: 19, 1, 9, 3, 10, 13. We want it to be sorted in ascending order.

We can now proceed with the comparison. You can notice that I've added indexes above each item of the list.

First iteration

• We start with the first and second item: 19 > 1 is true, so we need to swap both items.

Our list looks now like this:

• Next, we compare the second item with the third one: 19 > 9 is true, again we need to swap.

The new list is formed as follows:

• We proceed with the third and fourth items: 19 > 3 is true, we swap as before.

Again, our list is arranged like this:

• Let's continue the comparison with the fourth and the fifth items: 19 > 10 is true, once more we swap.

After swapping, the list is now as follows

• We proceed with the fifth item and the last one: 19 > 13 is true, we need to swap.

Thus, after swapping item 5 and item 6, the list becomes:

This is the end of the first iteration. Notice how the largest item (19) is at the last position. 10 and 13 are also at their position.

Second iteration

We will be doing the same thing as in the first iteration.

• We proceed with the first and the second items: 1 > 9 is false, so no swapping.

• Next, we proceed with 9 and 3: 9 > 3 is true, we swap.

After swapping, the list is now like this:

Every item is in its right position. This marks the end of the process.

Note: If the list was not yet sorted as expected, we could continue with the third, nth processes until we get a fully sorted list.

Bubble sort: Pseudocode

It's always a good practice to use pseudocode before actual implementation. This is one for the bubble sort.

function bubbleSort(arr)
Set isSwapped to true
WHILE isSwapped = true
    Reset isSwapped to false
    FOR each item in the arr
        IF current item > next item
            swap items
            Reset isSwapped to true
        ENDIF
    ENDFOR
ENDWHILE
RETURN arr

Bubble sort: Java implementation

Now is the time to implement the algorithm. We are using Java here. If you want a JavaScript implementation, use this link.

We create two classes:

• BubbleSort.java for the implementation of the logic
• Main.java to test the implementation

BubbleSort.java

Let's create a method called sort() and implement the first iteration.

public class BubbleSort {
    public void sort(int[] list) {
        for (int i = 0; i < list.length - 1; i++) {
            if(list[i] > list[i + 1]) {
                // swap is true
                int temp = list[i];
                list[i] = list[i + 1];
                list[i + 1] = temp;
            }
        }
    }

}

Our method is not that complicated. We're going through the list of integers by comparing adjacent items to see if they need to be swapped. If so, we do swap them. Look how we've implemented our swapping system:

• first, we keep the left item in temporary variable, temp
• next, we assign the value of the right item to the left one
• last, the right item is assigned temp

To make our code cleaner and more readable, let's move the swap logic into a method called swap().

private void swap(int[] list, int curr_index) {
  int temp = list[curr_index];
  list[curr_index] = list[curr_index + 1];
  list[curr_index + 1] = temp;
}

Our is working pretty fine, but only for one iteration, which is not enough to sort the list as expected.

Let's modify the code so that it can loop over and over until we get a fully sorted list.

public class BubbleSort {
    public void sort(int[] list) {
        boolean isSwapped = true;

        while (isSwapped) {
            isSwapped = false;
            for (int i = 0; i < list.length - 1; i++) {
                if(list[i] > list[i + 1]) {
                    isSwapped = true;
                    swap(list[i], list[i + 1]);
                }
            }
        }
    }

    private void swap(int left_item, int right_item) {
        int temp = left_item;
        left_item = right_item;
        right_item = temp;
    }

}

What did we do here? We've created a boolean variable, isSwapped and initialized to true so that we can use it in a while loop. Inside the while loop, we first assume that we want need swapping, so we set isSwapped to false. If we end up swapping, we reset it back to true.

We can now test our implementation.

Main.java

public class BubbleSort {
    public void sort(int[] list) {
        boolean isSwapped = true;

        while (isSwapped) {
            isSwapped = false;
            for (int i = 0; i < list.length - 1; i++) {
                if(list[i] > list[i + 1]) {
                    swap(list, i);
                    isSwapped = true;
                }
            }
        }
    }

    private void swap(int[] list, int curr_index) {
          int temp = list[curr_index];
          list[curr_index] = list[curr_index + 1];
          list[curr_index + 1] = temp;
    }

}

Congratulations! You've been able to implement Bubble sort algorithm in Java.

One more thing for your information: complexity of the algorithm

Complexity analysis

To end our journey, let me say just one word about the performance of this algorithm.

Bubble sort is a very simple sorting algorithm and also the very slow one. For this reason, you'll almost never find or use it in the real world. In fact, it is mostly used for educational purposes.

• Worst Case Time Complexity, aka Big-O: $O(n^2)$
• Best Case Time Complexity, aka Big-omega: $O(n)$
• Average Time Complexity, aka Big-theta: $O(n^2)$
• Space Complexity: $O(1)$

Happy coding!