Review

We started out by extending our pumpkin weighing program to tell us the highest two weights rather than just the highest one. During this exercise, we learned the use of the else clause of an if statement. We also saw that making even an apparently simple change to a working program can introduce an error; in this case we were copying the highest weight to the next highest weight only when a new high weight was detected. This would produce an incorrect result if a value higher than the previous second highest but lower than the current highest weight were entered.

Next we extended the program again, this time to handle any number of prizes to be given to the highest weight, second-highest weight, third-highest weights, and so on. This inspired a complete reorganization of the program; the new version used the selection sort algorithm to produce a list of as many of the highest weights as we need, in descending order. To do this, we had to use a Vec, or set of values with a common name, to store all of the weights as they were read in. When they had all been entered, we searched through them three times, once to find each of the top three elements. A Vec, just like a regular variable, has a name. However, unlike a regular variable, a Vec does not have a single value, but rather consists of a number of elements, each of which has a separate value. An element is referred to by a number, called an index, rather than by a unique name; each element has a different index. The lowest index is 0, and the highest index is 1 less than the number of elements in the Vec; for example, with a 10 element Vec, the legal indexes are 0 through 9. The ability to refer to an element by its index allows us to vary the element we are referring to in a statement by varying the index; we put this facility to good use in our implementation of the selection sort, which we'll review shortly.

We then added the for statement to our repertoire of loop control facilities. This statement provides more precise control than the while statement. Using for, we can specify a starting expression, a continuation expression, and a modification expression. The starting expression sets up the initial conditions for the loop. Before each possible execution of the controlled block, the continuation expression is checked and if it is true, the controlled block will be executed; otherwise, the for loop will terminate. Finally, the modification expression is executed after each execution of the controlled block. Most commonly, the starting expression sets the initial value of a variable, the continuation expression tests whether that variable is still in the range we are interested in, and the modification expression changes the value of the variable. For example, in the for statement

for (i = 0; i < 5; i ++)

the starting expression is i = 0, the continuation expression is i < 5, and the modification expression is i ++. Therefore, the block controlled by the for statement will be executed first with the variable i set to 0; at the end of the block, the variable i will be incremented by 1, and the loop will continue if i is still less than 5.

Then we used the for statement and a couple of Vecs to implement a selection sort. This algorithm goes through an “input list” of n elements once for each desired “result element”. In our case, we want the top three elements of the sorted list, so the input list has to be scanned three times. On each time through, the algorithm picks the highest value remaining in the list and adds that to the end of a new “output list”. Then it removes the found value from the input list. At the end of this process, the output list has all of the desired values from the input list, in descending order of size. When going over the program, we found a weak spot in the first version: If all the weights the user typed were less than or equal to 0, the program would fail because one of the variables in the program would never be initialized; that is, set to a known value.

This led to a discussion of why variable initialization isn't done automatically in C++. Adding this feature to programs would make them slower and larger than C programs doing the same task, and C++ was intended to replace C completely. If C++ programs were significantly less efficient than equivalent C programs, this would not be possible, so Bjarne Stroustrup omitted this feature.

While it's important to insure that our programs work correctly even when given unreasonable input, it's even better to prevent this situation from occurring in the first place. So, the next improvement we made to our pumpkin weighing program was to tell the user when an invalid value had been entered and ask for a valid value in its place. This involved a for loop without a modification expression, since we wanted to increment the index variable i to point to the next element of the Vec only when the user typed in a valid entry; if an illegal value was typed in, we requested a legal value for the same element of the Vec.