Python

O(n²):

def bubble_sort(array):
    length = len(array) - 1
    for _ in range(0, length):
        for i in range(0, length):
            j = i + 1
            bigger, smaller = array[i : j + 1]

            if bigger > smaller:
                array[i], array[j] = smaller, bigger

    return array


assert bubble_sort([1, 2, 3]) == [1, 2, 3], True
assert bubble_sort([3, 2, 1]) == [1, 2, 3], True
assert bubble_sort([2, 3, 1]) == [1, 2, 3], True
assert bubble_sort([1, 2, 3, 4]) == [1, 2, 3, 4], True
assert bubble_sort([4, 3, 2, 1]) == [1, 2, 3, 4], True
assert bubble_sort([1, 3, 2, 4]) == [1, 2, 3, 4], True
assert bubble_sort([4, 2, 7, 1, 3]) == [1, 2, 3, 4, 7], True
assert bubble_sort([1, 2, 3, 4, 7]) == [1, 2, 3, 4, 7], True
assert bubble_sort([4, 2, 7, 1, 3]) == [1, 2, 3, 4, 7], True
assert bubble_sort([1, 2, 3, 4, 7]) == [1, 2, 3, 4, 7], True