The Selection Sort

Now that we have stored all of the weights, we want to find the three highest of the weights. We'll use a sorting algorithm called a selection sort, which can be expressed in English as follows:

Let's take a look at the portion of our C++ program that implements this sort, in Figure 4.8.

Figure 4.8. Sorting the weights (from codevect1.cpp)

for (i = 0; i < 3; i ++)
  {
  HighestWeight = 0;
  for (k = 0; k < 5; k ++)
    {
    if (Weight[k] > HighestWeight)
      {
      HighestWeight = Weight[k];
      HighestIndex = k;
      }
   }
  SortedWeight[i] = HighestWeight;
  Weight[HighestIndex] = 0;
  }

Susan had some interesting comments and questions on this algorithm. Let's take a look at our discussion of the use of the variable i:

Susan: Now I understand why you used the example of i = i + 1; in Chapter 3; before, it didn't make sense why you would do that silly thing. Anyway, now let me get this straight. To say that, in the context of this exercise, means you can keep adding 1 to the value of i? I am finding it hard to see where this works for the number 7, say, or anything above 5 for that matter. So, it just means you can have 4 +1 or + another 1, and so on? See where I am having trouble?

Steve: Remember, a short variable such as i is just a name for a 2-byte area of RAM, which can hold any value between – 32768 and +32767. Therefore, the statement i ++; means that we want to recalculate the contents of that area of RAM by adding 1 to its former contents.

Susan: No, that is not the answer to my question. Yes, I know all that <G>. What I am saying is this: I assume that i ++; is the expression that handles any value over 4, right? Then let's say that you have pumpkins that weigh 1, 2, 3, 4, and 5 pounds consecutively. No problem, but what if the next pumpkin was not 6 but say 7 pounds? If at that point, the highest value for i was only 5 and you could only add 1 to it, how does that work? It just doesn't yet have the base of 6 to add 1 to. Now do you understand what I am saying?

Steve: I think I see the problem you're having now. We're using the variable i to indicate which weight we're talking about, not the weight itself. In other words, the first weight is Weight[0], the second is Weight[1], the third is Weight[2], the fourth is Weight[3], and the fifth is Weight[4]. The actual values of the weights are whatever the user of the program types in. For example, if the user types in 3 for the first weight, 9 for the second one, 6 for the third, 12 for the fourth, and 1 for the fifth, then the Vec will look like Figure 4.9.

Figure 4.9. Elements vs. values

The value of i has to increase by only one each time because it indicates which element of the Vec Weight is to store the current value being typed in by the user. Does this clear up your confusion?

Susan: I think so. Then it can have any whole number value 0 or higher (well, up to 32767); adding the 1 means you are permitting the addition of at least 1 to any existing value, thereby allowing it to increase. Is that it?

Steve: No, I'm not permitting an addition; I'm performing it. Let's suppose i is 0. In that case, Weight[i] means Weight[0], or the first element of the Weight Vec. When I add 1 to i, i becomes 1. Therefore, Weight[i] now means Weight[1]. The next execution of i ++; sets i to 2; therefore, Weight[i] now means Weight[2]. Any time i is used in an expression, for example, Weight[i], i + j, or i + 1, you can replace the i by whatever the current value of i is. The only place where you can't replace a variable such as i by its current value is when it is being modified, as in i ++ or the i in i = j + 1. In those cases, i means the address where the value of the variable i is stored.

Susan: OK, then i is not the number of the value typed in by the user; it is the location of an element in the Weight Vec, and that is why it can increase by 1, because of the i ++?

Steve: Correct, except that I would say “that is why it does increase by 1 ”. This may just be terminology.

Susan: But in this case it can increase no more than 4 because of the i < 5 thing?

Steve: Correct.

Susan: But it has to start with a 0 because of the i = 0 thing?

Steve: Correct.

Susan: So then cin >> Weight [i] means that the number the user is typing has to go into one of those locations but the only word that says what that location could be is Weight; it puts no limitations on the location in that Weight Vec other than when you defined the index variable as short i;. This means the index cannot be more than 32767.

Steve: Correct. The current value of i is what determines which element of Weight the user's input goes into.

Susan: I think I was not understanding this because I kept thinking that i was what the user typed in and we were defining its limitations. Instead we are telling it where to go.

Steve: Correct.

Having beaten that topic into the ground, let's look at the correspondence between the English description of the algorithm and the code:

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

HighestWeight = 0;

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

if (Weight[k] > HighestWeight)
   {
   HighestWeight = Weight[k];
   HighestIndex = k;
   }

SortedWeight[i] = HighestWeight;

Weight[HighestIndex] = 0;

This statement is the reason that we have to keep track of the “highest index”; that is, the index of the highest weight. Otherwise, we wouldn't know which element of the original Weight Vec we've used and therefore wouldn't be able to set it to 0 to prevent its being used again.

Here's Susan's rendition of this algorithm:

Susan: OK, let me repeat this back to you in English. The result of this program is that after scanning the list of user input weights the weights are put in another list, which is an ordering list, named k. The program starts by finding the highest weight in the input list. It then takes it out, puts it in k, and replaces that value it took out with a 0, so it won't be picked up again. Then it comes back to find the next highest weight and does the same thing all over again until nothing is left to order. Actually this is more than that one statement. But is this what you mean? That one statement is responsible for finding the highest weight in the user input list and placing it in k. Is this right?

Steve: It's almost exactly right. The only error is that the list that the weights are moved to is the SortedWeight Vec, rather than k. The variable k is used to keep track of which is the next entry to be put into the SortedWeight Vec.

Susan: OK. There was also something else I didn't understand when tracing through the program. I did see at one point during the execution of the program that i=5. Well, first I didn't know how that could be because i is supposed to be < 5, but then I remembered that i ++ expression in the for loop, so I wondered if that is how this happened. I forgot where I was at that point, but I think it was after I had just completed entering 5 values and i was incrementing with each value. But see, it really should not have been more than 4 because if you start at 0 then that is where it should have ended up.

Steve: The reason that i gets to be 5 after the end of the loop is that at the end of each pass through the loop, the modification expression (i ++) is executed before the continuation expression (i < 5). So, at the end of the fifth pass through the loop, i is incremented to 5 and then tested to see if it is still less than 5. Since it isn't, the loop terminates at that point.

Susan: I get that. But I still have a question about the line if (Weight[k] > HighestWeight). Well, the first time through, this will definitely be true because we've initialized HighestWeight to 0, since any weight would be greater than 0. Is that right?

Steve: Yes. Every time through the outer (i) loop, as we get to the top of the inner loop, the 0 that we've just put in HighestWeight should be replaced by the first element of Weight; that is, Weight[0], except of course if we've already replaced Weight[0] by 0 during a previous pass. It would also be possible to initialize HighestWeight to Weight[0] and then start the loop by setting k to 1 rather than 0. That would cause the inner (k) loop to be executed only four times per outer loop execution, rather than five, and therefore would be more efficient.

Susan: Then HighestIndex=k; is the statement that sets the placement of the highest number to its position in the Vec?

Steve: Right.

Susan: Then I thought about this. It seems that the highest weight is set first, then the sorting takes place so it makes four passes (actually five) to stop the loop.

Steve: The sorting is the whole process. Each pass through the outer loop locates one more element to be put into the SortedWeight Vec.

Susan: Then the statement Weight[HighestIndex] = 0; comes into play, replacing the highest number selected on that pass with 0.

Steve: Correct.

Susan: Oh, when k is going through the sorting process why does i increment though each pass? It seems that k should be incrementing.

Steve: Actually, k increments on each pass through the inner loop, or 15 times in all. It's reset to 0 on each pass through the outer loop, so that we look at all of the elements again when we're trying to find the highest remaining weight. On the other hand, i is incremented on each pass through the outer loop or three times in all, once for each “highest” weight that gets put into the SortedWeight Vec.

Susan: OK, I get the idea with i, but what is the deal with k? I mean I see it was defined as a short, but what is it supposed to represent, and how did you know in advance that you were going to need it?

Steve: It represents the position in the original list, as indicated in the description of the algorithm.

Susan: I still don't understand where k fits into this picture. What does it do?

Steve: It's the index in the “inner loop”, which steps through the elements looking for the highest one that's still there. We get one “highest” value every time through the “outer loop”, so we have to execute that outer loop three times. Each time through the outer loop, we execute the inner loop five times, once for each entry in the input list.

Susan: Too many terms again. Which is the “outer loop” and which is the “inner loop”?

Steve: The outer loop executes once for each “highest” weight we're locating. Each time we find one, we set it to 0 (at the end of the loop) so that it won't be found again the next time through.

Susan: OK, but now I am confused with the statement: if (Weight[k] > HighestWeight). This is what gets me: if I understand this right (and obviously I don't) how could Weight[k] ever be greater than HighestWeight, since every possible value of k represents one of the elements in the Weight Vec, and HighestWeight is the highest weight in that Vec? For this reason I am having a hard time understanding the code for step 2, but not the concept.

Steve: The value of HighestWeight at any time is equal to the highest weight that has been seen so far. At the beginning of each execution of the outer loop, HighestWeight is set to 0. Then, every time that the current weight (Weight[k]) is higher than the current value of HighestWeight, we reset HighestWeight to the value of the current weight.

Susan: I still don't understand this statement. Help.

Steve: Remember that HighestWeight is reset to 0 on each pass through the outer loop. Thus, this if statement checks whether the kth element of the Weight Vec exceeds the highest weight we've seen before in this pass. If that is true, obviously our “highest” weight isn't really the highest, so we have to reset the highest weight to the value of the kth element; if the kth element isn't the true highest weight, at least it's higher than what we had before. Since we replace the “highest” weight value with the kth value any time that the kth value is higher than the current “highest” weight, at the end of the inner loop, the number remaining in HighestWeight will be the true highest weight left in Weight. This is essentially the same algorithm as we used to find the highest weight in the original version of this program, but now we apply it several times to find successively lower “highest” weights.

Susan: OK, I understand now, i increments to show how many times it has looped through to find the highest number. You are doing a loop within a loop, really, it is not side by side is it?

Steve: Correct.

Susan: So, when you first enter your numbers they are placed in an index called i, then they are going to be cycled through again, placing them in a corresponding index named k, looking for the top three numbers. To start out through each pass, you first set the highest weight to the first weight since you have preset the highest weight to 0. But, to find the top three numbers you have to look at each place or element in the index. At the end of each loop you sort out the highest number and then set that removed element to 0 so it won't be selected again. You do this whole thing three times.

Steve: That's right, except for some terminology: where you say “an index called i”, you should say “a Vec called Weight”, and where you say “an index called k”, you should say “a Vec called SortedWeight”. The variables i and k are used to step through the Vecs, but they are not the Vecs themselves.

Susan: OK, then the index variables just are the working representation of what is going on in those Vecs. But are not the numbers “assigned” an index? Let's see; if you lined up your five numbers you could refer to each number as to its placement in a Vec. Could you then have the column of weights in the middle of the two indexes of i and k to each side?

Steve: If I understand your suggestion, it wouldn't work, because k and i vary at different speeds. During the first pass of the outer loop, i is 0, while k varies from 0 to 5; on the second pass of the outer loop, i is 1, while k varies from 0 to 5 again, and the same for the third pass of the outer loop. The value of i is used to refer to an individual element of the SortedWeight Vec, the one that will receive the next “highest” weight we locate. The value of k is used to refer to an individual element of the Weight Vec, the one we're examining to see if it's higher than the current HighestWeight.

Susan: This is what gets me, how do you know in advance that you are going to have to set HighestIndex to k? I see it in the program as it happens and I understand it then, but how would you know that the program wouldn't run without doing that? Trial and error? Experience? Rule books? <G>

Steve: Logic. Let's look at the problem again. The sorting algorithm that we're using here is called selection sort, because each time through the outer loop it selects one element out of the input Vec and moves it to the output Vec. To prevent our selecting the same weight (i.e., the highest one in the original input) every time through the outer loop, we have to clear each weight to 0 as we select it. But, to do that, we have to keep track of which one we selected; that's why we need to save HighestIndex.

The Selection Sort in More Detail

To help clear up any remaining questions Susan (and you) might have about this algorithm, let's go back and look at its steps more closely (they start on page 178). Steps 1 through 3 should be fairly self-explanatory, once you're familiar with the syntax of the for statement; they start the outer loop, initialize the highest weight value for the current loop, and start the inner loop.

Step 4 is quite similar to the process we went through to find the highest weight in our previous two programs; however, the reason for the HighestIndex variable may still need some more clarification. We need to keep track of which element of the original Vec (i.e., Weight) we have decided is the highest so far, so that this element won't be selected as the highest weight on every pass through the Weight Vec. To prevent this error, step 4 sets each “highest” weight to a value that won't be selected on a succeeding pass. Since we know there should be no 0 weights in the Weight Vec, we can set each selected element to 0 after it has been selected, to prevent its reselection. Figure 4.10 shows a picture of the situation before the first pass through the data, with ??? in SortedWeight to indicate that those locations contain unknown data, as they haven't been initialized yet.

In Figure 4.10, the highest value is 11 in Weight[2]. After we've located it and copied its value to SortedWeight[0], we set Weight[2] to 0, yielding the situation in Figure 4.11.

Now we're ready for the second pass. This time, the highest value is the 7 in Weight[4]. After we copy the 7 to SortedWeight[1], we set Weight[4] to 0, leaving the situation in Figure 4.12.

On the third and final pass, we locate the 5 in Weight[0], copy it to SortedWeight[2], and set Weight[0] to 0. As you can see in Figure 4.13, SortedWeight now has the results we were looking for: the top three weights, in descending order.

Making Assumptions Can Be Dangerous

That accounts for all the steps in the sorting algorithm. However, our implementation of the algorithm has a weak spot that we should fix. If you want to try to find it yourself, look at the code and explanation again before going on. Ready?

The key word in the explanation is “should” in the following sentence: “Since we know there should be no 0 weights in the Weight Vec, we can set each selected element to 0 after it has been selected, to prevent its reselection.” How do we know that there are no 0 weights? We don't, unless we screen for them when we accept input.

In the first pumpkin-weighing program, we stopped the input when we got a 0, but in the programs in this chapter we ask for a set number of weights. If one of them is 0, the program will continue along happily.^[14] Before we change the program, though, let's try to figure out what would happen if the user types in a 0 for every weight.

^[14] For that matter, what if someone types in a negative weight, such as – 5? Of course, this doesn't make any sense; but it's a good idea to try to prevent errors rather than assuming that users of a program will always act sensibly.

You can try this scenario out yourself. First, you have to compile the program vect1 by the usual method, then run the program, either normally or under the debugger. When it asks for weights, enter a 0 for each of the five weights.

In case you're reading this away from your computer, Figure 4.14 shows what might happen (although the element number in the message may not be the same)^[15].

^[15] It's even possible that you won't get an error message at all and the program will run correctly. However, if this happens, it just means that you're lucky. As you'll see later, you shouldn't count on that sort of luck.

Figure 4.14. A possible error message

You have tried to use element 68 of a vector which has only 5 elements.

Why doesn't the program work in this case? Because we have an uninitialized variable; that is, one that has never been set to a valid value. In this case, it's HighestIndex. Let's look at the sorting code one more time, in Figure 4.15.^[16]

^[16] You may have noticed a slight oddity in this code. The block controlled by the for statement consists of exactly one statement; namely, the if that checks for a new HighestWeight value. According to the rules I've provided, that means we don't have to put curly braces ({ }) around it to make it a block. While this is true, long experience has indicated that it's a very good idea to make it a block anyway, as a preventive measure. It's very common to revisit old code to fix bugs or add new functions, and in so doing we might add another statement after the if statement at a later time, intending it to be controlled by the for. The results wouldn't be correct, since the added statement would be executed exactly one time after the loop was finished, rather than once each time through the loop. Such errors are very difficult to find, because the code looks all right when inspected casually; therefore, a little extra caution when writing the program in the first place often pays off handsomely.

Figure 4.15. Sorting the weights, again (from codevect1.cc)

for (i = 0; i < 3; i ++)
  {
  HighestWeight = 0;
  for (k = 0; k < 5; k ++)
    {
    if (Weight[k] > HighestWeight)
      {
      HighestWeight = Weight[k];
      HighestIndex = k;
      }
    }
  SortedWeight[i] = HighestWeight;
  Weight[HighestIndex] = 0;
  }

It's clear that HighestWeight is initialized (i.e., given a valid value) before it is ever used; the statement HighestWeight = 0; is the first statement in the block controlled by the outer for loop. However, the same is not true of HighestIndex. Whenever the condition in the if statement is true, both HighestWeight and HighestIndex will indeed be set to legitimate values: HighestWeight will be the highest weight seen so far on this pass, and HighestIndex will be the index of that weight in the Weight Vec. However, what happens if the condition in the if statement never becomes true? In that case, HighestIndex will have whatever random value it started out with at the beginning of the program; it's very unlikely that such a value will be correct or even refer to an actual element in the Weight Vec.

Why We're Using Vec Rather Than vector

By the way, this illustrates the reason why we are using the Vec type rather than the standard library type vector; that error message comes from my code in the implementation of Vec, not from vector. If you try to refer to a nonexistent element of a vector, the results will be unpredictable. This is not a defect in the design of the vector type, by the way; because of the emphasis on speed in C++, that particular error check was left to be added by the programmer if he or she wants to add it. If the program is designed in such a way that no illegal reference can ever be made to an element of a vector, there is no necessity to slow it down by doing the error check all the time.^[17]

^[17] Although it would have been possible to make the normal indexing via [ ] do the check as we do in the Vec type and add another way to say “don't check the validity of this index”. That would be a better design, in my opinion.

However, even as a professional programmer of many years experience, I prefer to have the assurance that if I make a mistake in using a vector, or similar data type, I will be notified of it rather than having something go wrong that I don't know about, so I usually accept the performance penalty of such checking. Of course, this is even more important when you are just getting started, as you have much less experience to draw on to try to figure out why your program isn't working.

Uninitialized Variables

As you can imagine, Susan was interested in the notion of uninitialized variables. Here's the discussion we had on this topic:

Susan: You say that HighestIndex isn't initialized properly. But what about when you set k equal to 0 and then HighestIndex is set equal to k? Is that not initialized?

Steve: The problem is that the statement HighestIndex = k; is executed only when Weight[k] is greater than HighestWeight. If that never occurs, then HighestIndex is left in some random state.

Susan: OK, then why didn't you say so in the first place? I understand that. However, I still don't understand why the program would fail if all the weights the user typed in were 0. To me it would just have a very boring outcome.

Steve: That's the case in which HighestIndex would never be initialized; therefore, it would contain random garbage and would cause the program to try to display an element at some random index value.

Susan: I traced through the program again briefly tonight and that reminds me to ask you why you put the highest weight value to 1596 and the second-highest weight value to 1614?

Steve: I didn't. Those just happened to be the values that those memory locations had in them before they were initialized.

Susan: I was totally confused right from the beginning when I saw that. But did you do that to show that those were just the first two weights, and that they have not been, how would you say this, “ordered” yet? I don't know the language for this in computerese, but I am sure you know what I am saying.

Steve: Not exactly; those variables haven't been initialized at that point, so whatever values they might contain would be garbage.

Susan: So at that point they were just the first and second weights, or did you just arbitrarily put those weights in there to get it started? Anyway, that was baffling when I saw that.

Steve: Before you set a variable to a particular value, it will have some kind of random junk in it. That's what you're seeing at the beginning of the program, before the variables have been initialized.

Susan: OK, I am glad this happened, I can see this better, but whose computer did that? Was it yours or mine? I mean did you run it first and your computer did it, or was it my computer that came up with those values?

Steve: It's your computer. The program starts out with “undefined” values for all of the uninitialized variables. What this means in practice is that their values are whatever happened to be left around in memory at those addresses. This is quite likely to be different on your machine from what it is on mine or even on yours at a different time.

Susan: So something has to be there; and if you don't tell it what it is, the old contents of memory just comes up?

Steve: Right.

Susan: If it had worked out that the higher number had been in the first place, then I would have just assumed that you put that there as a starting point. I am really glad that this happened but I was not too happy about it when I was trying to figure it out.

Steve: See, it's all for your own good.

Susan: If that were the case, I would think it nearly impossible that we have the same values at any given address. How could they ever be remotely the same?

Steve: It's very unlikely that they would, unless the address was one that was used by very basic software such as DOS or Windows, which might be the same on our computers.

Susan: Anyway, then you must have known I was going to get “garbage” in those two variables, didn't you? Why didn't you advise me at least about that? Do you know how confusing it was to see that first thing?

Steve: Yes, but it's better for you to figure it out yourself. Now you really know it, whereas if I had told you about it in advance, you would have relied on my knowledge rather than developing your own.

I hope that has cleared up the confusion about the effect of an uninitialized variable in this example. But you may still be wondering why we have to initialize variables ourselves; surely they must have some value at any given time. Let's listen in on the conversation that Susan and I had about this point:

Susan: So, each bit in RAM is capable of being turned on or off by a 1 or a 0? Which one is on and which one is off? Or does that matter? How does this work electronically? I mean how does the presence of a 0 or a 1 throw the RAM into a different electronic state?

Steve: To be more exact, each “switch” is capable of existing in either the “on” or “off” state. The assignment of states to 1s and 0s is our notion, which doesn't affect the fact that there are exactly two distinct states the switch can assume, just like a light switch (without a dimmer). We say that if the switch is off, it's storing a 0, and if it's on, it's storing a 1.

Susan: What is the “normal state” of RAM: on or off?

Steve: It's indeterminate. That's one reason why we need to explicitly set our variables to a known state before we use them.

Susan: That didn't make sense to me originally, but I woke up this morning and the first thing that came to my mind was the light switch analogy. I think I know what you meant by indeterminate.

If we consider the light switch as imposed with our parental and financial values, it is tempting to view the “normal state” of a light switch as off. Hey, does the light switch really care? It could sit there for 100 years in the on position as easily as in the off position. Who is to say what is normal? The only consequence is that the light bulb will have been long burned out. So it doesn't matter, it really doesn't have a normal state, unless people decide that there is one.

Steve: What you've said is correct. The switch doesn't care whether it's on or off. In that sense, the “normal” position doesn't really have a definition other than one we give it.

However, what I meant by indeterminate is slightly different. When power is applied to the RAM, each bit (or to be more precise, a switch that represents that bit) could just as easily start out on as off. It's actually either one or the other, but which one is pretty much random so we have to set it to something before we know its value.

Susan: Oh, you broke my heart, when I thought I had it all figured out! Well, I guess it was OK, at least as far as the light switch was concerned, but then RAM and a light switch are not created equal. So RAM is pretty easy to please, I guess...

After that bit of comic relief, let's get back to the analysis of this program. It should be fairly obvious that if the user types in even one weight greater than 0, the if statement will be true when that weight is encountered, so the program will work. However, if the user typed in all 0 weights, the program would fail, as we saw before, because the condition in the if statement would never become true. To prevent this from causing program failure, all we have to do is to add one more line, the one in bold in Figure 4.16.

Figure 4.16. Sorting the weights, with correct initialization (from codevect2.cpp)

for (i = 0; i < 3; i ++)
  {
  HighestWeight = 0;
  HighestIndex = 0;
  for (k = 0; k < 5; k ++)
    {
    if (Weight[k] > HighestWeight)
      {
      HighestWeight = Weight[k];
      HighestIndex = k;
      }
    }
  SortedWeight[i] = HighestWeight;
  Weight[HighestIndex] = 0;
  }

Now we can be sure that HighestIndex always has a value that corresponds to some element of the Weight Vec, so we won't see the program fail as the previous one would.

You can try this scenario out yourself. First you have to compile the program vect2 by the usual method, then run the program, either normally or under the debugger. When it asks for weights, enter a 0 for each of the five weights.

After you've entered 5 weights, the program will start the sorting process. This time, entering five 0 weights will produce the expected result: the top three weights will all be 0.

By the way, it's also possible to initialize a variable at the same time as you define it. For example, the statement short i = 12; defines a short variable called i and sets it to the value 12 at the same time. This is generally a good practice to follow when possible; if you initialize the variable when you define it, you don't have to remember to write a separate statement to do the initialization.