## What will we cover?

- What is Bubble sort and how does it work?
- How to implement it in Python
- How to evaluate the time complexity of the Bubble sort algorithm

## What is Bubble sort and how does it work?

In this video the Bubble sort algorithm is explained. On a high level, it takes an unsorted list and returns it sorted.

## How to implement Bubble sort in Python

Well, notice the above description. It is straight forward and simple to implement. That is one of the beauties of the algorithm. Simple to understand. Simple to implement.

def bubble_sort(my_list): for i in range(len(my_list), 1, -1): for j in range(1, i): if my_list[j-1] > my_list[j]: my_list[j-1], my_list[j] = my_list[j], my_list[j-1]

An simple illustration of how you can use it.

import random def generate_random_list(n): my_list = [] for i in range(n): my_list.append(random.randint(0, n)) return my_list def bubble_sort(my_list): for i in range(len(my_list), 1, -1): for j in range(1, i): if my_list[j-1] > my_list[j]: my_list[j-1], my_list[j] = my_list[j], my_list[j-1] my_list = generate_random_list(20) print(my_list) bubble_sort(my_list) print(my_list)

## Evaluating the performance of Bubble sort

First of the algorithm has two for-loops. An outer and an inner for-loop. With an input of a list of length N, the loops will be iterated the following number of times.

- Outer for-loop: N times
- Inner for-loop: N-1 + N-2 + N-3 + … + 1 + 0 times

Knowing the formula

- N-1 + N-2 + … + 1 + 0 = (N-1)*N/2

We can add that the time complexity of Bubble sort is O(n^2).

But let’s try to experiment with real running data, to see if we can confirm that complexity.

To get run-times from the algorithm the cProfile library comes in handy. It is easy to use and gives good insights. A simple way to get run-times is to set it like this.

import random import cProfile def generate_random_list(n): return [random.randint(0, 4*n) for i in range(n)] def bubble_sort(my_list): for i in range(len(my_list), 1, -1): for j in range(1, i): if my_list[j-1] > my_list[j]: my_list[j-1], my_list[j] = my_list[j], my_list[j-1] def profile_bubble_sort(n): my_list = generate_random_list(n) bubble_sort(my_list) cProfile.run("profile_bubble_sort(10000)")

It will result in an output in the following manner.

56372 function calls in 11.056 seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 11.056 11.056 <string>:1(<module>) 1 0.000 0.000 11.055 11.055 BubbleSortProfiling.py:16(profile_bubble_sort) 1 0.000 0.000 0.034 0.034 BubbleSortProfiling.py:5(generate_random_list) 1 0.008 0.008 0.034 0.034 BubbleSortProfiling.py:6(<listcomp>) 1 11.021 11.021 11.021 11.021 BubbleSortProfiling.py:9(bubble_sort) 10000 0.010 0.000 0.022 0.000 random.py:200(randrange) 10000 0.005 0.000 0.027 0.000 random.py:244(randint) 10000 0.007 0.000 0.012 0.000 random.py:250(_randbelow_with_getrandbits) 1 0.000 0.000 11.056 11.056 {built-in method builtins.exec} 1 0.000 0.000 0.000 0.000 {built-in method builtins.len} 10000 0.001 0.000 0.001 0.000 {method 'bit_length' of 'int' objects} 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 16364 0.003 0.000 0.003 0.000 {method 'getrandbits' of '_random.Random' objects}

You get the time spend in *Bubble sort* by looking the highlighted line. In the column *cumtime* you get the time spend in total in the function.

By collecting the run-time for various sizes of lists, we get the following graph.

The graph has a O(n^2) growth as expected.