DS&A

Exercises: Algorithm Efficiency

Before attempting these exercises, you should read the posts on dynamic analysis and static analysis.

You will need the following two files:

• sorting.py — code for selection sort, insertion sort and merge sort.
• timing.py — for measuring running times.

You should read both files carefully, to see what functions they provide. To make use of these libraries, put both in the same directory, and run timing.py in Python’s interactive mode.

Exercises

1. Use the following code to compare the three sorting algorithms for lists of length 1000:
   • time_algorithm(selection_sort, 1000, 200)
   • time_algorithm(insertion_sort, 1000, 200)
   • time_algorithm(merge_sort, 1000, 200)
   Which algorithm is faster?
2. Which algorithm is faster for lists of length 10? What about length 100?
3. Use the following code to measure the running time of selection sort for list lengths up to 2000, with 100 repetitions each. This may take a few minutes to complete.
   • vary_list_length(selection_sort, 2000, 100, 100)
   Copy the output into a spreadsheet, and plot a chart showing how the running time depends on the list length.
4. Measure the running times for insertion sort and merge sort, for the same list lengths. Plot your results for all three algorithms on the same chart. Which algorithm is most efficient for long lists?
5. Change the generate_random_list function to investigate the effect of other kinds of input. Try:
   • Lists which are already in order.
   • Lists which are completely out of order.
   • Lists of strings, instead of numbers. (You will need a way to generate random strings.)

• Tags: 
• exercises, efficiency, dynamic analysis, algorithms