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 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

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 that the plot of time required versus the length of a list for bubble sort is exponential 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 built-in 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.