Algorithm

def bubble(a):
    """
    Implements the bubble sort algorithm.
    """

    for iterations in range(0, len(a) - 1):
        i = 0
        j = i + 1
        while i < (len(a) - iterations - 1):
            if a[i] > a[j]:
                temp = a[i]
                a[i] = a[j]
                a[j] = temp
            i = i + 1
            j = j + 1

    return a

Step by step

array = [1,0,3,4,2,5]

iterations = 0
    i = 0
    j = 1
    a[0] > a[1] | 1 > 0 | True
        a[0] = 0
        a[1] = 1
    array = [0,1,3,4,2,5]

    i = 1
    j = 2
    a[1] > a[2] | 1 > 3 | False

    i = 2
    j = 3
    a[2] > a[3] | 3 > 4 | False

    i = 3
    j = 4
    a[3] > a[4] | 4 > 2 | True
        a[3] = 2
        a[4] = 4
    array = [0,1,3,2,4,5]

    i = 4
    j = 5
    a[4] > a[5] | 4 > 5 | False

iterations = 1
    i = 0
    j = 1
    a[0] > a[1] | False

    [...]

    i = 2
    j = 3
    a[2] > a[3] | 3 > 2 | True
        a[2] = 2
        a[3] = 3
    array = [0,1,2,3,4,5]

iterations = 3
    [...]

iterations = 4
    [...]

array = [0,1,2,3,4,5]

Complexity analysis

Time

We do N - 1 iterations in the outer loop. In the inner loop, for the best case we do 1 iteration and in the worst case we do N iterations. Thus, the average case for the inner loop is N/2.

O(N) = (N-1) * (N/2) = (N²/2) - (N/2) ≈ N².

Space

We use the same array that is passed as argument and a few more variables, so the cost is: O(N) = N + K ≈ N.

Use cases

  • Use this algorithm in benchmarks to realize that you should have used any other algorithm.