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
- Start from the second element and iterate to the first sorted element (the end of array at the beginning).
- If the previous number is bigger than the current one – swap them.
- 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:
- 9, -3, 5, 0, 1
- -3, 9, 5, 0, 1
- -3, 5, 9, 0, 1
- -3, 5, 0, 9, 1
- -3, 5, 0, 1, 9
- -3, 5, 0, 1, 9 // -3 is smaller, so will bubble 5
- -3, 0, 5, 1, 9
- -3, 0, 1, 5, 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:
- Check out other sorting algorithms in Algorithms Tutorial