Lab 6: Algorithm Analysis
- Pick a partner.
- Help each other with the code as needed. Do not type for your partner
and avoid dictation, but
make sure your partner is able to finish the assignment.
- Make sure that your partner understands the mergesort enough to
take a test over it.
- Put your partner's name with yours in the header of the
- If your partner is unable to complete the lab, your maximum grade is a 90%.
Runtime Complexity of Sorts
Analysis of Insertion Sort pp. 264-266
- The insertion sort has nested for loops, each of which can take N iterations:
- If the list is already sorted, the inner for loop condition will fail everytime. Therefore,
if the list is sorted, the algorithm requires only N iterations.
- The number of times the inner loop executes is based on the number of inversions in
the list: an inversion is any two elements where the first element is larger than the second.
- The runtime of the insertion sort is O(I+N), where I is the number of inversions.
- A reverse sorted list has O(N2) inversions.
- The insertion sort is O(N2).
Analysis of the Mergesort pp. 276-279
- The time to mergesort 1 element is 1: Time (1) = 1
- Time (N) = 2 Time (N/2) + N
- (Time (N))/N = (Time(N/2))/(N/2) + 1
- (Time (N/2))/(N/2) = (Time(N/4))/(N/4) + 1
- (Time (N/4))/(N/4) = (Time(N/8))/(N/8) + 1 . . .
- (Time (2))/(2) = (Time(1))/(1) + 1
- Now if we add up the equations, we get (Time (N))/N = (Time(N))/N = (Time(1))/1 + log N.
- Therefore the runtime is O(N log N).
Analysis of the Bubblesort
Turn in your code and a Makefile to create
- Analyze the bubblesort.
- In a file called
bubblesort.txt, give the runtime complexity of the bubblesort
and why you believe it is the right complexity.
sendlab.212.302 6 *.cpp *.h Makefile