DEV Community

Abel Lifaefi Mbula
Abel Lifaefi Mbula

Posted on

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.

List with indexes

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.

Swapping item 1 and item 2

Our list looks now like this:

The new list

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

Swapping item 2 and item 3

The new list is formed as follows:

New list after swapping item 2 and item 3

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

Swapping item 3 and item 4

Again, our list is arranged like this:

New list after swapping item 3 and 4

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

Swapping item 4 and item 5

After swapping, the list is now as follows

New list after swapping item 4 and item 5

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

Swapping item 5 and item 6

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

New list after swapping item 5 and item 6

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.

1 is not greater than 9, no swapping

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

Swapping item 2 and item 3

After swapping, the list is now like this:

New list swapping item 2 and item 3

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
Enter fullscreen mode Exit fullscreen mode

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;
            }
        }
    }

}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
    }

}
Enter fullscreen mode Exit fullscreen mode

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;
    }

}
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (0)