# Bubble sort

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