bubble sort

Bubble sorting is when we take an unsorted array of objects and sort the array in place. This does not allow us to do a new instantiation of an array, so we utilize a temp variable for what is being worked on.

How it works

We have to iterate the list and compare each of the items to the prior item to determine if it needs to be moved. We have to go through each prior item to find the index that needs to be swapped.

Big-o

The bubble sort runs in very poor time, O(n^2). This is due to the best and worst case scenarios both being O(n) for comparisons.

	Best	Worst
passes	O(1)	O(n)
comparisons	O(n)	O(n)
total	O(n)	O(n^2)
	linear	quadratic

Sample implementation

This Python implementation includes Pytest tests that are parametrized.

def bubble_sort(list: List[int]) -> List[int]:

    length = len(list)

    for i in range(length-1):
        for j in range(0, length-i-1):
            if list[j] > list[j+1]:
                temp = list[j]
                list[j] = list[j+1]
                list[j+1] = temp
    return list


@pytest.mark.parametrize(
    "list",
    [
        ([4, 5, 3, 7, 7]),
        ([8]),
        ([8, 7]),
        ([3, 5, 4, 1, 2, 2, 3]),
    ],
)
def test_bubble_sort(list):

    list = bubble_sort(list)

    length = len(list)
    for i in range(length-1):
        for j in range(0, length-i-1):
            assert list[j] <= list[j + 1]