Algorithm details:

Worst-case Time Complexity: O(n^2)

Space Complexity: O(1)

 

The algorithm

Bubble sort is a very simple sorting algorithm, with straight forward implementation. The algorithm is based on comparison of all elements to each other. The compared element positions are switched on the comparison result, and the element is shifted to the correct location. This implies, that each element has to be checked against each other. This results in n*n comparisons, even if the collection is in order.

The algorithm itself is simple to implement, but it is not very efficient in terms of time complexity, compared to more advanced algorithms like Quick Sort or Merge sort. Most languages nowadays contain libraries with better time complexity by default. In Java the Util package contains a sort method, in the Arrays class. Based on the documentation the implementation is Dual-Pivot Quicksort which performs O(n log(n)) time complexity. For real world use-case, I would suggest to stick to the default package, as it offers much better performance compared to Bubble sort.

 

Java implementation

Bubble sort algorithm in ascending order

public static void sort(Comparable[] items) {
        int arrayLength = items.length;
        
        for (int i = 0; i < arrayLength; i++) {
            for (int j = 1; j < (arrayLength - i); j++) { if (items[j - 1].compareTo(items[j]) > 0) {
                    swapItems(items, j - 1, j);
                }
            }
        }
    }

    protected static void swapItems(Comparable[] items, int indexOne, int indexTwo) {
        Comparable tmp = items[indexOne];
        items[indexOne] = items[indexTwo];
        items[indexTwo] = tmp;
    }

The above code snippet is using the Comparable interface, to simplify the code. With a slight change it is possible to implement ordering of the sort, as:

     public static void sort(Comparable[] items, boolean sortAsc) {
        int arrayLength = items.length;
        
        for (int i = 0; i < arrayLength; i++) {
            for (int j = 1; j < (arrayLength - i); j++) { if ((sortAsc && items[j - 1].compareTo(items[j]) > 0)
                        || (!sortAsc && items[j - 1].compareTo(items[j]) < 0)) {
                    swapItems(items, j - 1, j);
                }
            }
        }
    }

    protected static void swapItems(Comparable[] items, int indexOne, int indexTwo) {
        Comparable tmp = items[indexOne];
        items[indexOne] = items[indexTwo];
        items[indexTwo] = tmp;
    }

The complete implementation with unit tests is available in my Java Algorithms Github Repo, https://github.com/pete314/algorithms-java

Share This