Merge, insertion or bubble: which is best?
Now that you have looked at three different sorting algorithms, you can have a go at investigating the efficiency of the two methods.
A good way to compare the efficiency of algorithms is to time how long they take to execute. That is what you are going to do in this step, run all three algorithms on the same list and see how long each method of sorting takes to execute.
I am going to show you a crude way to time your algorithms, using structures and modules you should be familiar with. Namely time and random.
from time import time
from random import randint
##################################################################################
# COPY AND PASTE YOUR bubble_sort, insertion_sort AND merge_sort functions below #
##################################################################################
#Generate a large (1000 items) random list
list_to_sort = []
for i in range(1000):
list_to_sort.append(randint(0, 100000))
# Capture the current time, before the algorithm has run
start_time = time()
# Run the merge sort algorithm
merge_sort(list_to_sort)
# Calculate the running time by taking the start time away from the current time, and display it.
print("Merge took: " + str(time() - start_time))
# Repeat the process for insertion sort...
start_time = time() # Capture start time
insertion_sort(list_to_sort) # Run the algorithm
print("Insertion took: " + str(time() - start_time)) #Display the results
# Repeat the process for bubble sort...
start_time = time() # Capture start time
bubble_sort(list_to_sort) # Run the algorithm
print("Bubble took: " + str(time() - start_time)) #Display the results
Using the values above, you’ll probably get results that look something like this:
Merge took: 0.005771160125732422
Insertion took: 0.052536964416503906
Bubble took: 0.13006091117858887
Now you can start to play with the algorithms and see how they compare to each other in different cases. See if you can answer the following questions:
How does the size of the unsorted list affect the speed of the algorithms?
Do the algorithms perform differently on very small lists?
How do the algorithms perform when they are given an already sorted list?
What happens if the lists are nearly sorted?
What happens when the lists are sorted in reverse order?
Share your answers to these questions in the comments section. Are there any other things you have discovered about the efficiency of these sorting algorithms?