Bubble Sort

April 17, 2019 2 minutes

Bubble Sort is one of the first sorting algorithms that is taught as part of any basic CS course. Even with its simple implementation, bubble sort is rarely used for large datasets or where efficient processing is required due to its quadratic, average and worst case run time complexity.

The algorithm is also known as comparison-sort and works on the method of swapping elements which are not at correct position. The idea is to compare adjacent elements in every iteration and if found to be out of place, those are swapped with each other.

This allows the smallest (or largest depending on the swap criteria) element to surface on the top. Consider the following example :

BubbleSort

This is the first pass of BubbleSort algorithm applied on input array : {5,2,8,1,3}. In every iteration of the pass, adjacent elements are compared to see if a swap is required or not. If the elements are out of order, a swap is performed on them.

Following this approach, subsequent passes of the BubbleSort algorithm applied on the array are :

  • Second Pass : {2, 5, 1, 3, 8} -> {2, 5, 1, 3, 8} -> {2, 1, 5, 3, 8} -> {2, 1, 3, 5, 8} -> {2, 1, 3, 5, 8}

  • Third Pass : {2, 1, 3, 5, 8} -> {1, 2, 3, 5, 8} -> {1, 2, 3, 5, 8} -> {1, 2, 3, 5, 8} -> {1, 2, 3, 5, 8}

Complexity

As clear from the above discussion, the bubble sort algorithm completes in $O(n^2)$ time and hence performs very poorly for large datasets as the runtime increase quadratically with the input size.

Java Implementation

public int[] sort(int[] input) {
    int length = input.length;
    for (int i = 0; i < length - 1; i++) {
        for (int j = 0; j < length - 1; j++) {
            int previous = j;
            int next = j + 1;

            //if out of order? swap these elements
            if (input[previous] > input[next]) {
               int temp = input[previous];
               input[previous] = input[next];
               input[next] = temp;
            }
        }
    }
    return input;
}

A working java implementation with test cases can be found here

comments powered by Disqus