Bubble sort – bubble sort in Java

Sorting algorithms are used to reorder the elements of an array or list in ascending or descending numerical or lexicographic order. Data sorting is very important for the optimal performance of other algorithms that require sorted input data. There are a number of different sorting algorithms. The selection of an appropriate algorithm depends on factors such as the size and characteristics of the input data, available memory, and time and space requirements. To make your choice easier, in our series we will introduce the most well-known data sorting algorithms, explain their principles, advantages and disadvantages, and program them in Java. Today we are going to look at bubble sorting.

Bubble sort algorithm

Bubble sort is a sorting algorithm that compares every two adjacent elements in turn and discards them until they are sorted in the desired order. The algorithm requires multiple iterations. The name of the algorithm is derived from the air bubbles that rise to the surface in water. Analogously in the algorithm, the elements of the array bubble up in each iteration to the end of the unsorted portion of the array.

Bubble sort algorithm – working principle

Suppose we want to sort the elements in ascending order. If an array has only one element, it is considered sorted, otherwise the elements need to be sorted.

First iteration:

All two adjacent array elements are compared sequentially from the beginning of the array. If the first element is larger than the second, they swap order. Then the second element is compared with the third, the third with the fourth, and so on. The first iteration ends by comparing the last neighbouring elements. During the first iteration, swapping elements is guaranteed to get the largest element of the array to the end of the array.

Other iterations:

The last index of the array is considered sorted, the rest of the array is not sorted yet. For the unsorted part of the array, the procedure from the first iteration is repeated. Each iteration bubbles the largest element to the end of the unsorted portion of the array. This is repeated until the field is sorted. Number of iterations: n-1
Number of comparisons: n*(n-1)/2

Example

We have the following array of elements [3][1][2]. From the formulas, we can calculate that the number of required iterations is 2, and the number of comparisons is 6. In the first iteration, the following operations take place: [1][3][2] -> [1][2][3]. The largest element 3 was mapped to the last index of the array. Even though the array is already sorted, a second iteration is performed which compares the first two elements of the array and since the first and second elements have the correct order, there is no swapping of their order.

Optimizing Bubble Sort Algorithm

In the example above, we saw that if we already have the array sorted, additional iterations and comparisons are still performed unnecessarily. This of course increases the running time of the algorithm. The solution is to note at each iteration whether there is a change in the order of any two elements. If not, we consider the array to be sorted and do not perform subsequent iterations. This optimization will reduce the time complexity for the already sorted array and ensure the adaptivity of the algorithm.

Advantages of the Bubble sort algorithm

  • It is easy to understand and implement
  • Does not require additional memory when sorting
  • It is stable, that is, two identical elements from the input retain their relative order in the result

Disadvantage of the Bubble sort algorithm

  • The time complexity is O(n²), which makes it a slow algorithm for a large dataset

Bubble sort time consumption

Algorithm Method Time complexity Memory Stable
worst average best
Bubble sort exchange O(n²) O(n²) O(n) O(1) Yes

Bubble sort animation, visualization, gif

A visualization of the Bubble sort algorithm looks like this:

bubble sort animation
Swfung8, CC BY-SA 4.0, via Wikimedia Commons
bubble sort animation
Cocrider69, CC BY-SA 4.0, via Wikimedia Commons

Source: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms

You can find an animation of the algorithm for example at Toptal. There are 8 types of algorithms, you can also play the animation backwards. On this page you can go through the steps of the algorithm to check the time consumption of the algorithm.

Bubble Sort Implementation – Example in Java

Let’s program an optimized version of bubble sort in Java. BubbleSort.java

package sorting;

// An optimized version of Bubble Sort
public class BubbleSort {
    private boolean change;
    private int temp;

    public void sort(int data[])
    {
        for (int i = 0; i < data.length - 1; i++) {
            System.out.println(i + 1 + ". iteration");
            change = false;
            for (int j = 0; j < data.length - i - 1; j++) {
                if (data[j] > data[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    change = true;
                    printArray(data);
                }
            }
            // If no two elements swapped, then end the sort method
            if (!change)
                return;
        }
    }

    // Function to print an array
    public void printArray(int data[])
    {
        for (int i = 0; i < data.length; i++)
            System.out.print(data[i] + " ");
        System.out.println();
    }
}

Main.java

import sorting.BubbleSort;

public class Main {
    public static void main(String[] args) {
        int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
        BubbleSort bubbleSort = new BubbleSort();
        System.out.print("Input: ");
        bubbleSort.printArray(dataToSort);
        bubbleSort.sort(dataToSort);
        System.out.print("Sorted: ");
        bubbleSort.printArray(dataToSort);
    }
}

The output of this example is: Bubble sort example output We have prepared the files with the above example in the form of code that you can run directly in Java. Download the BubbleSort code inJava here. If you’re a Java developer looking for a job, check out our employee benefits and respond to our job offers.

About the author

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.

Let us know about you