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 sort them using bubble sort and 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 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 installing matplotlib
# 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
As you can see that that plot of time required versus length of a list for bubble sort is exponential increasing. It is not exponential, but it is quadratic since time complexity for bubble sort is O(n2) whereas time against the length of the list plot for builtin function is reasonably linear.
With the help of 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.
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 🙂