Search

Bubble Sort

Bubble Sort (or sinking sort) is a straight-forward comparison sort algorithm that continuously compares adjacent indexes and swaps them if they are out of order.

Table of contents

Performance

Best
Ω(n)
Average
Θ(n2)
Worst
O(n2)

Code

public class BubbleSort {
    public static void main(String[] args)
    {
        int[] array = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
        BubbleSort sorter = new BubbleSort();
        sorter.bubbleSort(array);
        System.out.println(java.util.Arrays.toString(array));
    }

    void bubbleSort(int[] array)
    {
        int n = array.length;
        while (n > 0)
        {
            int lastModifiedIndex = 0;
            for (int currentIndex = 1; currentIndex < n; currentIndex++)
            {
                // if the item at the previous index is greater than the item at the `currentIndex`, swap them
                if (array[currentIndex - 1] > array[currentIndex])
                {
                    // swap
                    int temp = array[currentIndex - 1];
                    array[currentIndex - 1] = array[currentIndex];
                    array[currentIndex] = temp;
                    // save the index that was modified
                    lastModifiedIndex = currentIndex;
                }
            }
            // save the last modified index so we know not to iterate past it since all proceeding values are sorted
            n = lastModifiedIndex;
        }
    }
}
public class BubbleSortGeneric<T extends Comparable<? super T>> {
    public static void main(String[] args)
    {
        // example using Strings
        String[]                  arrayOfStrings = {"Andree", "Leana", "Faviola", "Loyce", "Quincy", "Milo", "Jamila", "Toccara", "Nelda", "Blair", "Ernestine", "Chara", "Kareen", "Monty", "Rene", "Cami", "Winifred", "Tara", "Demetrice", "Azucena"};
        BubbleSortGeneric<String> stringSorter   = new BubbleSortGeneric<>();
        stringSorter.bubbleSort(arrayOfStrings);
        System.out.println(java.util.Arrays.toString(arrayOfStrings));

        // example using Doubles
        Double[]                  arrayOfDoubles = {0.35, 0.02, 0.36, 0.82, 0.27, 0.49, 0.41, 0.17, 0.30, 0.89, 0.37, 0.66, 0.82, 0.17, 0.20, 0.96, 0.18, 0.25, 0.37, 0.52};
        BubbleSortGeneric<Double> doubleSorter   = new BubbleSortGeneric<>();
        doubleSorter.bubbleSort(arrayOfDoubles);
        System.out.println(java.util.Arrays.toString(arrayOfDoubles));
    }

    void bubbleSort(T[] array)
    {
        int n = array.length;
        while (n > 0)
        {
            int lastModifiedIndex = 0;
            for (int currentIndex = 1; currentIndex < n; currentIndex++)
            {
                // if the item at the previous index is greater than the item at the `currentIndex`, swap them
                if (array[currentIndex - 1].compareTo(array[currentIndex]) > 0)
                {
                    // swap
                    T temp = array[currentIndex - 1];
                    array[currentIndex - 1] = array[currentIndex];
                    array[currentIndex] = temp;
                    // save the index that was modified
                    lastModifiedIndex = currentIndex;
                }
            }
            // save the last modified index so we know not to iterate past it since all proceeding values are sorted
            n = lastModifiedIndex;
        }
    }
}
#include <iostream>
#include <vector>

void bubbleSort(std::vector<int> &arr) {
    int n = static_cast<int>(arr.size());
    while (n > 0) {
        int lastModifiedIndex = 0;
        for (int currentIndex = 1; currentIndex < n; currentIndex++) {
            // if the item at the previous index is greater than the item at the `currentIndex`, swap them
            if (arr[currentIndex - 1] > arr[currentIndex]) {
                // swap
                int temp = arr[currentIndex - 1];
                arr[currentIndex - 1] = arr[currentIndex];
                arr[currentIndex] = temp;
                // save the index that was modified
                lastModifiedIndex = currentIndex;
            }
        }
        // save the last modified index so we know not to iterate past it since all proceeding values are sorted
        n = lastModifiedIndex;
    }
}

int main() {
    std::vector<int> arr = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
    bubbleSort(arr);
    for (int i; i < arr.size(); i++) {
        std::cout << arr[i];
        if (i < arr.size() - 1) std::cout << ", ";
    }
}
func bubbleSort(array: inout [Int]) {
    var n = array.count
    while (n > 0) {
        var lastModifiedIndex = 0
        for currentIndex in 1..<n {
            // if the item at the previous index is greater than the item at the `currentIndex`, swap them
            if array[currentIndex - 1] > array[currentIndex] {
                // swap
                let temp = array[currentIndex - 1]
                array[currentIndex - 1] = array[currentIndex]
                array[currentIndex] = temp
                // save the index that was modified
                lastModifiedIndex = currentIndex
            }
        }
        // save the last modified index so we know not to iterate past it since all proceeding values are sorted
        n = lastModifiedIndex
    }
}

var array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
bubbleSort(array: &array)
print(array)
function bubbleSort(array) {
  let n = array.length
  while (n > 0) {
    let lastModifiedIndex = 0
    for (let currentIndex = 1; currentIndex < n; currentIndex++) {
      // if the item at the previous index is greater than the item at the `currentIndex`, swap them
      if (array[currentIndex - 1] > array[currentIndex]) {
        // swap
        let temp = array[currentIndex - 1]
        array[currentIndex - 1] = array[currentIndex]
        array[currentIndex] = temp
        // save the index that was modified
        lastModifiedIndex = currentIndex
      }
    }
    // save the last modified index so we know not to iterate past it since all proceeding values are sorted
    n = lastModifiedIndex
  }
}

let array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
bubbleSort(array)
alert(array)
def bubble_sort():
    n = len(array)
    while (n > 0):
        lastModifiedIndex = 0
        currentIndex = 1
        while (currentIndex < n):
            # if the item at the previous index is greater than the item at the `currentIndex`, swap them
            if (array[currentIndex - 1] > array[currentIndex]):
                # swap
                temp = array[currentIndex - 1]
                array[currentIndex - 1] = array[currentIndex]
                array[currentIndex] = temp
                # save the index that was modified
                lastModifiedIndex = currentIndex
            currentIndex += 1
            # save the last modified index so we know not to iterate past it since all proceeding values are sorted
        n = lastModifiedIndex

if __name__ == '__main__':
    array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
    bubble_sort(array)
    print(array)

Walkthrough

The algorithm executes in the following steps:

  1. Start at the beginning of the array
  2. Compare the first item to the second
  3. If the items are out of order, swap them and step forward in the array
  4. Continue doing this until you reach the end of the array
  5. Each pass through the array will always end with at least one value being placed at the correct index

Using this algorithm, larger values get pushed to the end of the array faster than smaller values. Similarly, under water, larger bubbles rise to the top faster than smaller bubbles. So, it’s fitting that this algorithm would be called Bubble Sort!

Discussion