Evaluate the performance of sorting algorithms

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

1. Language: Python3

2. IDE: Spyder

3. Libraries used:

4. randint in random: to generate random integers

5. timeit: to find out the execution time

6. 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 🙂