Here is a summary of what I asked you do to for class on Monday, October 29^th. The next exam will be on Monday November 5, one week from the 29^th and will cover material from Chapters 8 and 9 in the Friedman/Koffman text.

Reread the material on desk-checking algorithms (see especially the tables on p 202 and p. 235) in the Friedman/Koffman text. Then set up two sheets of paper, each organized pretty much the way p. 235 is laid out. On one sheet you will record your trace of the sort function. On the second sheet, you will record your trace of the find-index-of-smallest-element function each time it is called. Using the data given in class (an array x with 6 elements – unsorted), desk check the C++ code for the selection sort algorithm worked out in class last Wednesday. Each time the function find-index-of-smallest-element function is called stop the trace of the sort function and follow the trace of the find-index… function. When the find-index… function completes execution, then take up the trace of the sort right where it had left off, but with the index of the smallest element returned to the sort. You need not trace the exchange function as I assume you know what it does.

1. Start with a trace of the sort function itself, passing in the array x and a value of n = 6. Again:
2. Trace the sort
3. When the sort calls the find-index… function, go to the other sheet and trace this function
4. When the find-index… function returns the index to the sort, go back to the sort trace and continue with it.
5. Keep doing this until the sort returns.

Your array should now be sorted in ascending order.

ALSO:

1. How many calls are made to find-index…when n=6? ______
2. For each call to find_index…, how many comparisons are made? ______________________
3. Can you write out a mathematical expression that indicates the TOTAL number of comparisons made for when n = 6? Try it.