Bubble Sort in Java

Introduction

Sorting is a crucial aspect of digesting data. For us humans, it's much more natural to sort things that have something in common like the date of publishing, alphabetical order, articles belonging to an author, from smallest to largest, etc...

This makes it a lot easier to comprehend the data as it's logically connected rather than dispersed all around.

Human sorting is intuitive and simple, and thus often inefficient. We're usually not working with more than two elements we wish to sort. Computers are able to store huge amounts of data and element locations in their memory, which allow them to sort collections in a way humans couldn't, not to mention the speed of accessing/moving elements.

Bubble Sort

Bubble Sort is, in most cases, the first sorting algorithm any computer science enthusiast will encounter. It's the simplest and most intuitive sorting algorithms, which is one of the main reasons why it's taught to novice programmers/students.

It works by swapping adjacent elements, according to an order criteria. For example, if we want to sort a collection's elements from the smallest to largest - if the first element is larger than the second, they're swapped. This simple exchange is repeated with adjacent indexes until the collection is eventually sorted.

The exit condition for the algorithm is when we iterate through the whole collection without swapping a single element - which means it's fully sorted.

Here's a visual representation of how bubble sort works:

As you can see, the name itself comes from the visual illusion of elements "bubbling up" to their desired place. If you follow a certain element, say, 8 - you can notice it "bubbling up" to it's correct place in this example.

Implementation

With a brief overview of the theory behind Bubble Sort out of the way, let's implement it by sorting two different types of collections. First, we'll sort a simple array, and afterwards we'll sort an ArrayList with a custom object and a compareTo() method.

Sorting Arrays

Let's start out by sorting a simple array of integers:

public void bubbleSort(int[] array) {
    boolean sorted = false;
    int temp;
    while (!sorted) {
        sorted = true;
        for (int i = 0; i < array.length - 1; i++) {
            if (a[i] > a[i+1]) {
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                sorted = false;
            }
        }
    }
}

The sorted flag is used to signal if the array is sorted or not. If there's no reason to swap any element, or rather a[i] is always less than a[i+1] in a given iteration, the sorted flag is never reset to false.

Since it stays true, the array is sorted and we break out of the loop.

Running this piece of code:

int[] array = new int[]{5, 6, 7, 2, 4, 1, 7};
bubbleSort(array);
System.out.println(Arrays.toString(array));

Will yield:

[1, 2, 4, 5, 6, 7, 7]

Note: Since arrays are treated as objects in Java, having a void return type is absolutely valid when sorting arrays, and the contents are not copied at face-value when using it as an argument. In this case the array is sorted "in place".

Sorting ArrayLists

A more common scenario would be sorting an ArrayList populated by non-numerical objects. These can be employees, results from a database, users, etc. Since we don't know ahead of time how to sort these objects, it will need to be provided by the caller via the comapreTo() method.

Let's define a class for our objects that'll be stored in a collection:

public class Element {
    private int id;

    public Element(int id) {
        this.id = id;
    }

    // Getters and setters

    public int compareTo(Element element) {
        int res = 0;
        if (this.id < element.getId()) {
            res =- 1;
        }
        if (this.id > element.getId()) {
            res = 1;
        }
        return res;
    }
}

It's a very simple class with a single field - id. We can also @Override the toString() method if we'd like to print the results, but for the sake of brevity, let's not do that here and simply use the getId() method instead.

When it comes to sorting ArrayLists, since we're working with objects it's a little different than sorting simple arrays of primitive values since we can't just use relational operators.

Now, our compareTo() method simply compares the ids and returns -1 if the id of the current element is lesser than the element we're comparing it to, 1 if the id of the current element is higher, or 0 if they are equal.

Really, you can implement the comparing functionality in any way you'd like.

Now, let's implement Bubble Sort again:

public void bubbleSortArrayList(List<Element> list) {
    Element temp;
    boolean sorted = false;

    while (!sorted) {
        sorted = true;
        for (int i = 0; i < list.size()-1; i++) {
            if (list.get(i).compareTo(list.get(i + 1)) > 0) {
                temp = list.get(i);
                list.set(i, list.get(i + 1));
                list.set(i + 1, temp);
                sorted = false;
            }
        }
    }
}

This is pretty straightforward code, practically the same as the code in the example with arrays, utilizing the methods provided by the List interface.

Now, let's populate an ArrayList with a few elements:

List<Element> list = new ArrayList<>();

// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
    list.add(new Element(i));
}

// Move the elements to a random order
Collections.shuffle(list);

And we can sort it:

// Print list before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));

// Sort the list
bubbleSort.bubbleSortArrayList(list);

System.out.println();

// Print sorted list
list.forEach(e -> System.out.print(e.getId() + ", "));

As expected, the output is:

17, 13, 14, 5, 15, 22, 24, 7, 3, 9, 21, 10, 1, 11, 18, 20, 12, 8, 4, 19, 0, 23, 16, 2, 6,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,

The Collections API

A great thing about the Collections API that ships with Java 8 is helper methods that allow you to quickly and easily sort collections. We just need to implement the Comparable interface for the elements we wish to sort later on.

Let's change our Element class so that it implements the Comparable interface:

public class Element implements Comparable<Element> {
    private int id;

    // Constructor, getters and setters

    @Override
    public int compareTo(Element element) {
        int res = 0;
        if (this.id < element.getId()) {
            res =- 1;
        }
        if (this.id > element.getId()) {
            res = 1;
        }
        return res;
    }
}

As you can see, the Element class is pretty much the same as before. This time, we implemented the Comparable interface and overridden it's compareTo() method with the same logic as before.

Now, we can simply call Collections.sort() on our list:

List<Element> list = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    list.add(new Element(i));
}

Collections.shuffle(list);

// Print shuffled list
list.forEach(e -> System.out.print(e.getId() + ", "));

// Sort the list
Collections.sort(list);

System.out.println();

// Print sorted list
list.forEach(e -> System.out.print(e.getId() + ", "));

The sort() method from the Collections API uses Quick Sort to sort the given collection. This results in huge performance benefits compared to Bubble Sort, but we'll save that for another article.

Time Complexity

The time complexity (both average and worst) of Bubble Sort is O(n^2). This is, realistically observing, horrible for a sorting algorithm.

Albeit horrible, here's how the algorithm performed when sorting 10,000 objects in a collection:

List<Element> list = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    list.add(new Element(i));
}

Collections.shuffle(list);

// Print shuffled collection
list.forEach(e -> System.out.print(e.getId() + ", "));

long startTime = System.nanoTime();
bubbleSort.bubbleSortArrayList(list);
long endTime = System.nanoTime();

// Print sorted collection
list.forEach(e -> System.out.print(e.getId() + ", "));

System.out.println();

// Print runtime in nanoseconds
System.out.println("Bubble Sort runtime: " + (endTime - startTime));

And here are the results in seconds after running it 10 times:

With an average runtime of ~0.5s for 10,000 objects, will you really need algorithms that perform better? Most of the time, not really, unless you have an application with a high load that requires a fast response time.

If you're doing more complex comparisons than just comparing ids and have a huge collection, much larger than this one - yes, using an advanced algorithm with a much better time complexity will affect your performance significantly.

For reference, the sort() method from the Collections API sorted this same array of 10,000 elements in just 0.01s consistently. So even if there's no real need to sort your collections faster than 0.5s, using a built-in sorter provided by the Collections API will both save you time when coding and improve your application.

Conclusion

Bubble Sort is, in most cases, the first sorting algorithm any computer science enthusiast will encounter. It's the simplest and most intuitive sorting algorithm which is one of the main reasons why it's being taught at an early point.

We saw that this simple sorting algorithm works by swapping adjacent elements, according to a given order criteria. For example, if we want to sort a collection's elements from the smallest to largest - if the first element is larger than the second, they're swapped. This simple exchange is repeated for adjacent indexes until the collection is eventually sorted.

It's horribly inefficient and given that there are much more efficient algorithms built-in to Java in the Collections API, we'd advise that you don't use this algorithm for any production applications.