Bubble sort – Coding algorithms for interview

Let’s take a look at the bubble sort. Bubble sort is a sorting algorithm that is widely used for students’ education and it has many modifications.

The idea behind bubble sort is that the sorting step is to traverse the array from bottom to top. Pairs of neighboring elements are looked through along the way. If the elements of some pair are in the wrong order, then we swap them.

Let’s arrange the array from top to bottom. From the zero elements to the last.

As a result of the zero passes, the minimum element “floats” up – hence the name of the algorithm – bubble sort. We repeat the algorithm for all elements, except for the zero-one – it is already in its place. And we find the second largest element. We repeat the algorithm until the elements are sorted.

Let’s take a look at the Java bubble sort program implementation now.

The outer for loop is responsible for the pass number, and the inner loop is for iterating through the elements in one pass. Values ​​are exchanged using the temporary variable tmp. In the inner loop, we iterate over the values ​​starting from the last one (array.length - 1) and in each next pass, we reduce the number of elements scanned (j > i).

public class BubbleSorter {
    public static void sort(int[] array) {
        // i - iteration number
        for (int i = 0; i < array.length - 1; i++) { // inner loop itertation number 
            for (int j = array.length - 1; j > i; j--) {
                if (array[j - 1] > array[j]) {
                    int tmp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }
}

We will call the BubbleSorter.sort() method from the BubbleSorterTest class below. Let’s sort each row of the multidimensional array data:

import java.util.Arrays;

public class BubbleSorterTest {
    public static void main(String[] args) {
        int[][] data = {
                {},
                {1},
                {0, 3, 2, 1},
                {4, 3, 2, 1, 0},
                {6, 8, 3, 123, 5, 4, 1, 2, 0, 9, 7},
        };
        for (int[] arr : data) {
            System.out.print(Arrays.toString(arr) + " => ");
            BubbleSorter.sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }
}

Here is a table with the most well-known sort algorithms and complexity: