1 |
h07 |
CS32 F19 |
Name: | ||||
---|---|---|---|---|
(as it would appear on official course roster) | ||||
Umail address: | @umail.ucsb.edu | section 9am, 10am, 11am, 12pm |
||
Optional: name you wish to be called if different from name above. | ||||
Optional: name of "homework buddy" (leaving this blank signifies "I worked alone" |
h07: Sorting
ready? | assigned | due | points |
---|---|---|---|
true | Tue 10/22 02:00PM | Tue 10/29 02:00PM |
You may collaborate on this homework with AT MOST one person, an optional "homework buddy".
MAY ONLY BE TURNED IN IN THE LECTURE LISTED ABOVE AS THE DUE DATE,
OR IF APPLICABLE, SUBMITTED ON GRADESCOPE. There is NO MAKEUP for missed assignments;
in place of that, we drop the lowest scores (if you have zeros, those are the lowest scores.)
Reading: Sorting, DS 13.1
- (10 pts) Fill in the information in the header. The following are required to get the 10 "participation" points.
- Filling in your name and umail address.
Also: For paper submission PLEASE submit on ONE SHEET OF PAPER, double-sided if at all possible. If you must submit on two printed sheets write name on BOTH sheets and no staples, paperclips, or folded corners.
Please also read the handout http://cs.ucsb.edu/~richert/cs32/misc/h07-handout.pdf
- Filling in your name and umail address.
- (10 pts) BRIEFLY: What does it mean to say that an algorithm has "quadratic" worse case running time?
- 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 any passes with no swaps.
- Show the steps of sorts indicated following the example of the solved problems on the handout for the algorithm and the format of your answer.
(5 pts) Use insertion sort
initial
values35 95 12 34 28 i=0 i=1 i=2 i=3 i=4 (5 pts) Use insertion sort
initial
values70 50 20 80 10 i=0 i=1 i=2 i=3 i=4 - Show the steps of sorts indicated following the example of the solved problems on the handout for the algorithm and the format of your answer.
(5 pts) Use selection sort. SHOW ALL ROWS even for passes where there are no swaps.
initial
values35 95 12 34 28 i=4 i=3 i=2 i=1 (5 pts) Use selection sort. SHOW ALL ROWS even for passes where there are no swaps.
initial
values70 50 20 80 10 i=4 i=3 i=2 i=1
(5 pts) Use bubble sort. Stop after any pass with no swaps.
initial values |
35 | 95 | 12 | 34 | 28 |
i=4 | |||||
i=3 | |||||
i=2 | |||||
i=1 |
(5 pts) Use bubble sort. Stop after any pass with no swaps.
initial values |
70 | 50 | 20 | 80 | 10 |
i=4 | |||||
i=3 | |||||
i=2 | |||||
i=1 |