Bubble Sort

Published on , Updated on algorithm algorithm sorting time-complexity

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.

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)`.

• 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.

Set Size Maximum Value Bubble Sort Time Insertion Sort Time
10 10 0.04383 seconds 0.02296 seconds
1000 1000 5.54610 seconds 2.67873 seconds
10000 10000 68.60219 seconds 30.98420 seconds

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")

``````