Name:
Laboratory 9 Answer Sheet
Due at the beginning of class, Wednesday, 4/16
1 a, b and 2c. Comparing Sorting functions
Fill in the tables below with the results for running each of the different sorting algorithms
for a sorted list, reverse sorted list and random list for n = 10, 20 and 100.
Table 1. Number of comparisons for sorted lists:
| List Length | n = 10 | n = 20 | n = 100 | Formula | Expected for n=100 |
| Insertion Sort | |||||
| Sorted | |||||
| Reverse Sorted | |||||
| Random Sorted | |||||
| Selection Sort | |||||
| Sorted | |||||
| Reverse Sorted | |||||
| Random Sorted | |||||
| Merge Sort | |||||
| Sorted | ---- | ---- | |||
| Reverse Sorted | ---- | ---- | |||
| Random Sorted | nlgn + O(n) | ||||
| Quick Sort | |||||
| Sorted | ---- | ---- | |||
| Reverse Sorted | ---- | ---- | |||
| Random Sorted | nlgn + O(n) | ||||
| Bubble Sort | |||||
| Sorted | |||||
| Reverse Sorted | |||||
| Random Sorted | |||||
Problem 1d.
How do the sorting algorithms compare for each of the types of lists tested
(sorted in order, sorted in reverse order, random)? How do you think the number
or comparisons for Merge and Quick sort would compare to a function that increased
linearly (Do they increase faster, slower or about the same as a linear function)?
Problem 2b.
What is the formula for the number of comparisons performed by bubble sort in
each of the conditions tested? How did you arrive at this formula?
Problem 2c.
How does the performance of bubble_sort() compare to the other sorting functions tested
in this lab?
Please write your name at the top of this answer sheet and turn it in with the rest of the lab.