Bubble Sort

In the bubble sort algorithm, each pair of consecutive elements are swapped if they are not in the correct order. In each iteration, it places an element at its right place. Thus in n iterations, all n elements are sorted accordingly.

Bubble sort characteristics

Impractical

Bubble sort is one of the fundamental sorting algorithms to learn how sorting works. It is not a practical sorting algorithm for its poor performance. Though bubble sort has the same time complexity as insertion sort, insertion sort is more efficient than bubble sort.

Adaptive

Bubble sort is adaptive. Bubble sort performs best when the input data set is already sorted.

Offline

Bubble sort works after receiving all the data. It does not sort the element when it receives them.

Stable

Bubble sort is stable. Numbers with the same value appear in the output array as they appear in the input array. Let's take an input array A = [3, 0, 3]. In the input array, the value 3 occurs two times; at index 0 and 2. Insertion sort ensures that in the output array, the occurrences of 3 are placed in the same order as the input array.

In place:

Bubble sort sorts the input list in place. It does not require an additional list to sort the elements. It only requires a constant amount of extra memory space O(1).

Quadratic time complexity

It has quadratic time complexity.

• Worst Time complexity (Big-O): O(n*n), where n: total number of elements in the list.
  
• Average Time complexity (Big-Theta): Θ(n*n), where n: total number of elements in the list.
  
• Best Time complexity (Big-Omega): Ω(n), where n: total number of elements in the list.
  
• Space complexity: O(1)

Bubble Sort algorithm pseudocode

procedure Bubble_Sort(A: list of items)
    for i=0 to A.length-1 inclusive do
        swapped := false
        for j=0 to A.length-i-2 inclusive do
            if A[j] > A[j+1] then
                swap(A[j], A[j+1])
                swapped := true
            end if
        end for
        if not swapped then
            break
        end if
    end for
end procedure

Bubble Sort implementation using Python 3

"""
Implementation of bubble sort algorithm

Main File: bubble_sort.py
Test File: test_bubble_sort.py
"""


def get_bubble_sorted_numbers(numbers):
    """ Returns sorted list for a given list

    Arguments:
    numbers -- list of numbers
    """
    for i in range(len(numbers)):
        swapped = False
        for j in range(len(numbers) - i - 1):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
                swapped = True
        if not swapped:
            break
    return numbers

Unit testing bubble sort implementation using Python 3

"""
Unittest of bubble sort implementation

Test File: test_bubble_sort.py
Main File: bubble_sort.py
"""
import unittest
from bubble_sort import get_bubble_sorted_numbers


class TestBubbleSort(unittest.TestCase):
    def test_get_bubble_sorted_numbers_positive_unsorted(self):
        test_case = [2, 3, 1, 4, 2, 4]
        expected_result = sorted(test_case)
        test_result = get_bubble_sorted_numbers(test_case.copy())
        self.assertEqual(expected_result, test_result,
                         f"Failed on {test_case}, "
                         f"Expected {expected_result}, "
                         f"Found {test_result}")

    def test_get_bubble_sorted_numbers_positive_negative_unsorted(self):
        test_case = [2, -3, 1, -4, 2, 4]
        expected_result = sorted(test_case)
        test_result = get_bubble_sorted_numbers(test_case.copy())
        self.assertEqual(expected_result, test_result,
                         f"Failed on {test_case}, "
                         f"Expected {expected_result}, "
                         f"Found {test_result}")

    def test_get_bubble_sorted_numbers_same_values_positive(self):
        test_case = [1, 1, 1, 1]
        expected_result = sorted(test_case)
        test_result = get_bubble_sorted_numbers(test_case.copy())
        self.assertEqual(expected_result, test_result,
                         f"Failed on {test_case}, "
                         f"Expected {expected_result}, "
                         f"Found {test_result}")

    def test_get_bubble_sorted_numbers_same_values_negative(self):
        test_case = [-1, -1, -1]
        expected_result = sorted(test_case)
        test_result = get_bubble_sorted_numbers(test_case.copy())
        self.assertEqual(expected_result, test_result,
                         f"Failed on {test_case}, "
                         f"Expected {expected_result}, "
                         f"Found {test_result}")

    def test_get_bubble_sorted_numbers_single_item(self):
        test_case = [1]
        expected_result = sorted(test_case)
        test_result = get_bubble_sorted_numbers(test_case.copy())
        self.assertEqual(expected_result, test_result,
                         f"Failed on {test_case}, "
                         f"Expected {expected_result}, "
                         f"Found {test_result}")

    def test_get_bubble_sorted_numbers_empty_list(self):
        test_case = []
        expected_result = sorted(test_case)
        test_result = get_bubble_sorted_numbers(test_case.copy())
        self.assertEqual(expected_result, test_result,
                         f"Failed on {test_case}, "
                         f"Expected {expected_result}, "
                         f"Found {test_result}")

    def test_get_bubble_sorted_numbers_positive_negative_reverse(self):
        test_case = [1, 0, -1]
        expected_result = sorted(test_case)
        test_result = get_bubble_sorted_numbers(test_case.copy())
        self.assertEqual(expected_result, test_result,
                         f"Failed on {test_case}, "
                         f"Expected {expected_result}, "
                         f"Found {test_result}")

    def test_get_bubble_sorted_numbers_negative_reverse(self):
        test_case = [-1, -3, -56]
        expected_result = sorted(test_case)
        test_result = get_bubble_sorted_numbers(test_case.copy())
        self.assertEqual(expected_result, test_result,
                         f"Failed on {test_case}, "
                         f"Expected {expected_result}, "
                         f"Found {test_result}")

    def test_get_bubble_sorted_numbers_positive_negative_floating(self):
        test_case = [-1.5, 3.336, -66.3, 5]
        expected_result = sorted(test_case)
        test_result = get_bubble_sorted_numbers(test_case.copy())
        self.assertEqual(expected_result, test_result,
                         f"Failed on {test_case}, "
                         f"Expected {expected_result}, "
                         f"Found {test_result}")


if __name__ == "__main__":
    unittest.main()

Comparison between bubble sort and insertion sort

• Insertion sort is more efficient than bubble sort as it requires fewer swaps to sort the elements.
• Insertion sort is online, but bubble sort is offline. That means insertion sort sorts the elements when receiving each element but bubble sort sorts the elements only after receiving all the elements.

The following table shows the comparison between insertion sort and counting sort based on the execution time.

This result is generated using timeit module of Python with the following code.

"""
Compare execution time between insertion sort and counting sort
"""
from timeit import timeit
import random


def get_bubble_sorted_numbers(numbers):
    """ Returns a sorted list of numbers using bubble sort

    Arguments:
    numbers -- list of numbers
    """
    for i in range(len(numbers)):
        swapped = False
        for j in range(len(numbers) - i - 1):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
                swapped = True
        if not swapped:
            break
    return numbers


def get_insertion_sorted_numbers(numbers):
    """ Returns a sorted list of numbers using insertion sort

    Arguments:
    numbers -- list of numbers
    """
    for i in range(1, len(numbers)):
        value = numbers[i]
        j = i - 1
        while j >= 0 and numbers[j] > value:
            numbers[j + 1] = numbers[j]
            j -= 1
        numbers[j + 1] = value
    return numbers


if __name__ == "__main__":
    MAX_NUMBER = 10
    small_list = [random.randint(0, MAX_NUMBER) for i in range(MAX_NUMBER)]
    bubble_execution_time = timeit(
        'result=get_bubble_sorted_numbers(small_list.copy())',
        globals=globals(), number=10000)
    insertion_execution_time = timeit(
        'result=get_insertion_sorted_numbers(small_list.copy())',
        globals=globals(), number=10000)
    print(f"Data set of {MAX_NUMBER} numbers:")
    print(f"Bubble sort took: {bubble_execution_time:.5f} seconds")
    print(f"Insertion sort took: {insertion_execution_time:.5f} seconds")

    MAX_NUMBER = 1000
    medium_list = [random.randint(0, MAX_NUMBER) for i in range(MAX_NUMBER)]
    bubble_execution_time = timeit(
        'result=get_bubble_sorted_numbers(medium_list.copy())',
        globals=globals(), number=100)
    insertion_execution_time = timeit(
        'result=get_insertion_sorted_numbers(medium_list.copy())',
        globals=globals(), number=100)
    print(f"Data set of {MAX_NUMBER} numbers:")
    print(f"Bubble sort took: {bubble_execution_time:.5f} seconds")
    print(f"Insertion sort took: {insertion_execution_time:.5f} seconds")

    MAX_NUMBER = 10000
    large_list = [random.randint(0, MAX_NUMBER) for i in range(MAX_NUMBER)]
    bubble_execution_time = timeit(
        'result=get_bubble_sorted_numbers(large_list.copy())',
        globals=globals(), number=10)
    insertion_execution_time = timeit(
        'result=get_insertion_sorted_numbers(large_list.copy())',
        globals=globals(), number=10)
    print(f"Data set of {MAX_NUMBER} numbers:")
    print(f"Bubble sort took: {bubble_execution_time:.5f} seconds")
    print(f"Insertion sort took: {insertion_execution_time:.5f} seconds")

Practice challenges

Easy difficulty challenges:

• Bubble sort - Hackerearth
• Bubble sort - Geeksforgeeks

Reference

• Competitive Programmer's Handbook
• Bubble sort Wikipedia article
• Insertion sort
• Introduction to algorithms by Cormen, Thomas H and Leiserson, Charles E and Rivest, Ronald L and Stein, Clifford
• Counting sort
• Sorting Algorithm Comparisons
• Understanding Time Complexity
• timeit module documentation