Homework 7: Sorting
Due: 05/04 12:30pm
Name & Perm # (no partners allowed):
Reading: DS 13.1, also review DS 12.1, 2.6, 6.1
Please also read the handout at http://cs.ucsb.edu/~richert/cs32/misc/h07-handout.pdf
1. \( \) (10 pts)
Briefly explain: What does it mean to say that an algorithm has quadratic worst-case run time?
2. \( \)
Show the steps of bubble sort following the example of the solved problems on the handout for the algorithm and the format of your answer. Stop after the first pass with no swaps.
2.1. 5 pts
| initial values | 8 | 5 | 3 | 10 | 2 |
|---|---|---|---|---|---|
| i = 4 | |||||
| i = 3 | |||||
| i = 2 | |||||
| i = 1 |
2.2. 5 pts
| initial values | 40 | 42 | -3 | 10 | 0 |
|---|---|---|---|---|---|
| i = 4 | |||||
| i = 3 | |||||
| i = 2 | |||||
| i = 1 |
3. \( \)
Show the steps of insertion sort following the example of the solved problems on the handout for the algorithm and the format of your answer.
3.1. 5 pts
| initial values | 8 | 5 | 3 | 10 | 2 |
|---|---|---|---|---|---|
| i = 0 | |||||
| i = 1 | |||||
| i = 2 | |||||
| i = 3 | |||||
| i = 4 |
3.2. 5 pts
| initial values | 40 | 42 | -3 | 10 | 0 |
|---|---|---|---|---|---|
| i = 0 | |||||
| i = 1 | |||||
| i = 2 | |||||
| i = 3 | |||||
| i = 4 |
4. \( \)
Show the steps of selection sort following the example of the solved problems on the handout for the algorithm and the format of your answer. Show all rows even for passes that no swaps occur.
4.1. 5 pts
| initial values | 8 | 5 | 3 | 10 | 2 |
|---|---|---|---|---|---|
| i = 4 | |||||
| i = 3 | |||||
| i = 2 | |||||
| i = 1 |
4.2. 5 pts
| initial values | 40 | 42 | -3 | 10 | 0 |
|---|---|---|---|---|---|
| i = 4 | |||||
| i = 3 | |||||
| i = 2 | |||||
| i = 1 |