0

Bubble Sort is a sorting algorithm that repeatedly goes through an array and swaps adjacent elements that are not in order. In this post we’ll show how to implement it.

How it works

  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.

Bubble Sort properties

  • 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 ;-)

Example

Here’s a small example how bubbling numbers works:

  1. 9, -3, 5, 0, 1
  2. -3, 9, 5, 0, 1
  3. -3, 5, 9, 0, 1
  4. -3, 5, 0, 9, 1
  5. -3, 5, 0, 1, 9
  6. -3, 5, 0, 1, 9 // -3 is smaller, so will bubble 5
  7. -3, 0, 5, 1, 9
  8. -3, 0, 1, 5, 9
  9. -3, 0, 1, 5, 9 // all is sorted, so no swap

Bubble Sort implementation

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;
    }
}

Unit tests

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);
    }
}

References:

Share with the World!