Skip to content

Yet another programming solutions log

Sample bits from programming for the future generations.

Technologies Technologies
  • Algorithms and Data Structures
  • Java Tutorials
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Spock Framework Tutorial
  • Spring Framework
  • Bash Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Developer’s Tools
  • Productivity
  • About
Expand Search Form

Bubble Sort in Java

farenda 2016-10-01 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:

  • Check out other sorting algorithms in Algorithms Tutorial
Share with the World!
Categories Algorithms Tags algorithms, java
Previous: Linux head tail – display lines of file by example
Next: Groovy for Java Developers

Recent Posts

  • Java 8 Date Time concepts
  • Maven dependency to local JAR
  • Caesar cipher in Java
  • Java casting trick
  • Java 8 flatMap practical example
  • Linked List – remove element
  • Linked List – insert element at position
  • Linked List add element at the end
  • Create Java Streams
  • Floyd Cycle detection in Java

Pages

  • About Farenda
  • Algorithms and Data Structures
  • Bash Tutorial
  • Bean Validation Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Java 8 Streams and Lambda Expressions Tutorial
  • Java Basics Tutorial
  • Java Collections Tutorial
  • Java Concurrency Tutorial
  • Java IO Tutorial
  • Java Tutorials
  • Java Util Tutorial
  • Java XML Tutorial
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Software Developer’s Tools
  • Spock Framework Tutorial
  • Spring Framework

Tags

algorithms bash bean-validation books clojure design-patterns embedmongo exercises git gof gradle groovy hateoas hsqldb i18n java java-basics java-collections java-concurrency java-io java-lang java-time java-util java-xml java8 java8-files junit linux lists log4j logging maven mongodb performance quartz refactoring regex rest slf4j solid spring spring-boot spring-core sql unit-tests

Yet another programming solutions log © 2021

sponsored