Sorting algorithms are aplenty with different time and space complexities. In your textbooks, you will find that this algorithm has a time complexity of O(n2), that algorithm has a time complexity of O(n), but how you will prove it experimentally?

In this experiment, we will be generating lists with lengths varying from 1 to 1000 and sorting them using bubble sort and a built-in function using Python. You can use this snippet to evaluate the performance of your sorting algorithm.

This article does not try to find out which algorithm is better or poorer, but it just tries to compare them using the time required to execute the algorithm versus the length of the list.

The experimental setup goes as follows

Language: Python3

IDE: Spyder

Libraries used:

randint in random: to generate random integers

timeit: to find out the execution time

matplotlib: to plot graphs. If matplotlib is not installed, you can install it using

```
>>pip install matplotlib
```

Alternatively, you can use __this guide__ to install matplotlib

## Code

```
# import randint to generate list of random integers
from random import randint
# import timeit to findout time requried to execute a function
import timeit
# import matplotlib to plot graphs
import matplotlib.pyplot as plt
lengths = range(1, 1000)
times_for_bubble_sort = []
times_for_builtin_function = []
# generate lists with length starting from 1 to 1000
for l in lengths:
# generate a list with random integers ranging from -100 to 100
# and store it in two variables so that we can use the same list for
# different algorithms
generated_list = my_list = [randint(-100, 100) for x in range(0, l)]
# start bubble sort timer
start_time_bubble_sort = timeit.default_timer()
# bubble sort
for i in range(0, l-1):
for j in range(i+1, l):
if my_list[i] > my_list[j]:
temp = my_list[j]
my_list[j] = my_list[i]
my_list[i] = temp
# calculate time required to execute sorting fucntion and store it
# in a list
times_for_bubble_sort.append(timeit.default_timer() - start_time_bubble_sort)
# get original list
my_list = generated_list
# start timer for builtin function
start_time_builtin_function = timeit.default_timer()
# execute builting sorting function
sorted(my_list)
# calculate time required to execute bultin sorting function and store it
# in a list
times_for_builtin_function.append(timeit.default_timer() - start_time_builtin_function)
# plot the time vs length graph
# create a matplotlib figure
fig = plt.figure()
# subplot for bubble sort
ax1 = fig.add_subplot(211)
ax1.set_title("Bubble Sort")
ax1.set_ylabel("Time")
ax1.plot(lengths, times_for_bubble_sort)
# subplot for builtin function
ax2 = fig.add_subplot(212)
ax2.set_title("Builtin Function")
ax2.set_xlabel("Length of list")
ax2.set_ylabel("Time")
ax2.plot(lengths, times_for_builtin_function)
# show the plot
plt.show()
```

After executing the above code, the following plots were generated

### Output

As you can see the plot of time required versus the length of a list for bubble sort is exponentially increasing. It is not exponential, but it is quadratic since the time complexity for bubble sort is O(n2) whereas time against the length of the list plot for the builtin function is reasonably linear.

With the help of the above snippet, you can experimentally prove the time complexities of the various sorting algorithms. Also, if you are writing any custom sorting function, you can benchmark it against different other algorithms.

## Note:

I am no more writing regarding Python or programming on this __blog, __as I have shifted my focus from programming to WordPress and web development. If you are interested in WordPress, you can continue reading other articles on this blog.

Thanks and Cheers 🙂

## Kommentare