# Python - Bubble Sort Algorithm Implementation

Bubble sort algorithm - In this article, we will learn about one of the sorting algorithms - Bubble sort. Time complexity of this algorithm is O(n^2) and space complexity being O(1).

#### Bubble Sort Algorithm

```for i = 0 to [length(array) - 1]
begin
# To keep track of whether a swap has happened
flag = 0

# Last 'i' elements will always be sorted
for j = 0 to [length(array) - i - 1]
begin

# Check if array[j] > array[j+1], Swap if True
if array[j] > array[j+1]
begin
swap array[j] and array[j+1]
flag = 1
endif
endfor

if flag == 0
begin
break
endif

endfor

return array
```

#### Example

Consider the following list-

Here, length of the array is 8, hence there outer loop, which we will refer to as a pass, will be executed 8 times, while inner loop will be executed (8 - 0 - 1) times. Lets see the first pass.

Pass 1-1:

```i = 0, j = 0
array = 5, array[0+1] = 3
array > array
Result - 5 and 3 will be swapped.
```

Pass 1-2:

```i = 0, j = 1
array = 5, array[1+1] = 7
array < array
Result - Nothing happens
```

Pass 1-3:

```i = 0, j = 2
array = 7, array[2+1] = 1
array > array
Result - 7 and 1 will be swapped
```

Pass 1-4:

```i = 0, j = 3
array = 7, array[3+1] = 4
array > array
Result - 7 and 4 will be swapped
```

Pass 1-5:

```i = 0, j = 4
array = 7, array[4+1] = 8
array < array
Result - Nothing happens
```

Pass 1-6:

```i = 0, j = 5
array = 8, array[5+1] = 2
array > array
Result - 8 and 2 will be swapped
```

Pass 1-7:

```i = 0, j = 6
array = 8, array[6+1] = 6
array > array
Result - 8 and 6 will be swapped
```

Observation - After once complete pass, it can be observed that, the largest element in the array is bubbled up to the last position in the array. In another words, after one pass, one element in the array is sorted. Also, if no swap happens, it can be concluded that the array is sorted and we can break out of the loop. To keep track of this, we have introduced variable `flag` in the algorithm.

Similarly, after subsequent passes, array will look like -

After the 5th pass, there will be no swapping. Hence there is no need for more iterations and the process can be stopped.

#### Python Implementation:

```def bubble_sort(array):
n = len(array)

for i in range(n):
flag = 0

for j in range(n-i-1):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
flag = 1

if flag == 0:
break

my_array = [5, 3, 7, 1, 4, 8, 2, 6]
bubble_sort(my_array)
print my_array
```

Output:

```[1, 2, 3, 4, 5, 6, 7, 8]
```