1
h07
CS32 F20
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 Thu 10/22 09:00AM Thu 11/05 11:59PM

You may collaborate on this homework with AT MOST one person, an optional "homework buddy".

MAY ONLY BE TURNED IN ON GRADESCOPE BEFORE THE DUE DATE,
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

  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.
    2. Please also read the handout http://cs.ucsb.edu/~richert/cs32/misc/h07-handout.pdf
  2. (10 pts) BRIEFLY: What does it mean to say that an algorithm has "quadratic" worse case running time?
  3. 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.

    4. (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          
  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 insertion sort

    initial
    values     		 35   95   12   34   28 
    i=0          
    i=1          
    i=2          
    i=3          
    i=4          

    (5 pts) Use insertion sort

    initial
    values     		 70   50   20   80   10 
    i=0          
    i=1          
    i=2          
    i=3          
    i=4          
  5. 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
    values     		 35   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
    values     		 70   50   20   80   10 
    i=4          
    i=3          
    i=2          
    i=1