## 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 > a | 1 > 0 | True
a = 0
a = 1
array = [0,1,3,4,2,5]

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

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

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

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

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

[...]

i = 2
j = 3
a > a | 3 > 2 | True
a = 2
a = 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.