1. Start from the second element and iterate to the first sorted element (the end of array at the beginning).
2. If the previous number is bigger than the current one – swap them.
3. Repeat while there are swaps, which means that the array is sorted.

• average and worst case complexity is O(n^2)
• the best case (array already sorted) complexity is O(n)
• memory complexity in O(1), because the algorithm reuses the same array
• has a catchy name ;-)

package com.farenda.tutorials.algorithms.sorting;

public class BubbleSort {

    public void sort(int[] numbers) {
        boolean swapped;
        int n = numbers.length;
        do {
            swapped = false;
            int lastSorted = n;
            for (int i = 1; i < n; ++i) {
                if (numbers[i-1] > numbers[i]) {
                    swap(numbers, i-1, i);
                    swapped = true;
                    // All above the last swap is already sorted:
                    lastSorted = i;
                }
            }
            n = lastSorted;
        } while (swapped);
    }

    private void swap(int[] values, int first, int second) {
        int tmp = values[first];
        values[first] = values[second];
        values[second] = tmp;
    }
}

package com.farenda.tutorials.algorithms.sorting;

import org.junit.Test;

import static org.junit.Assert.assertArrayEquals;

public class BubbleSortTest {

    private BubbleSort sorter = new BubbleSort();

    @Test
    public void shouldDoNothingWithEmptyArray() {
        int[] values = {};

        sorter.sort(values);
    }

    @Test
    public void shouldDoNothingWithOneElementArray() {
        int[] values = {42};

        sorter.sort(values);

        assertArrayEquals(new int[] {42}, values);
    }

    @Test
    public void shouldSortValues() {
        int[] values = { 9, -3, 5, 0, 1};
        int[] expectedOrder = { -3, 0, 1, 5, 9};

        sorter.sort(values);

        assertArrayEquals(expectedOrder, values);
    }
}