Iteration using for (Part 4)

When to choose for instead of while

Now that we have so many options, how do we know which type of loop to use? Our example of searching in a string demonstrated when “for” loop might be simpler and clearer than the “while” loop.

The function using while loop: define search(word, char) index ← 0 while index < length(word) if word[index] == char return index index ← index + 1 return index

The function using for loop: define search(word, char) for index from to length(word)-1 if word[index] == char return index return length(word)

In general, this will occur when the counter is used in a simple way to process elements in a string or sequence. So choose for loop when it is simpler and clearer.

For our remainder example, we saw that "while" was simpler and clearer than "for".

The function using the while loop: define remainder(first, second) while first >= second first ← first - second return first

The function using the for loop: define remainder(first, second) result ← first for counter from 1 to first result ← result - second if result < second break return result

This often occurs when the condition is more complex than comparing the counter to the length of a string or sequence. So, again, choose while loop when it is simpler and clearer.

Example: merging two sorted sequences

There are also situations when while is really the only choice. To illustrate this concept, consider a program that consumes two sorted sequences, A and B, and forms a new sequence, C, with all items in order. Let's choose these two sequences to be A = [5, 6, 9, 11, 15, 18] and B = [3, 4, 8, 10, 13]:

How can we use iteration? We can form the new sequence by iteratively finding the smallest item. Initially, the smallest item will be in the first position of one of the two sequences. Hence, we compare A[0] = 3 and B[0] = 5, and choose the smaller one, so C[0] = 3. The next smallest item is now either in the first position of the first sequence, or in the second position of the second sequence. Why? Remember, each of these sequences is in sorted order, so there cannot be a smaller item lurking somewhere farther back in one of the sequences. So, Again, we compare A[0] = 5 and B[1] = 4, choose the smaller number and update the new sequence, C[1] = 4, and change the focus of our investigation to the next number. We are now comparing A[1] = 5 and B[2] = 8 and since 5 is smaller, we set C[2] = 5 and now compare A[1] = 6 and B[2] = 8. Again, we select the smaller item, set C[3] = 6, and change our focus, this time to A[2] = 9 and B[2] = 8. We add 8 to the new sequence, C[4] = 8, and now consider A[2] = 9 and B[3] = 10. Since 9 is smaller, we set C[5] = 9 and we now compare A[3] = 11 and B[3] = 10, resulting in 10 being added to the new sequence, hence C[6] = 10. Comparing A[3] = 11 and B[4] = 13 results in setting C[7]=11, and comparing A[4] = 15 and B[4] = 13 results in setting C[8] = 13. One of our sequences is now empty, so what can we do? We know that we can just copy over the rest of the remaining sequence to complete the merge. So C[9] = 15 and C[10] = 18. The new sequence we formed is shown below:

Since we were interleaving progress on the two sequences in an unpredictable way, the flexibility of a while loop makes it possible to write the program. So choose while when for is too limited.

Writing the program

We first write the pseudocode for the first stage of the program up until one of the sequences has been used up. That is, we keep going until we have reached the end of one of the sequences, which we call one and two. We give initial values to the position markers and the new sequence we are creating. At each iteration, we compare the current items, that is, those in positions pos_one and pos_two. When the smaller item is in the first sequence, we copy that element to our new sequence and update pos_one. Otherwise, we copy the element in the second sequence to our new sequence and update pos_two. We now need to add the pseudocode for copying over any elements that remain in one of the sequences. Here is how to copy any elements left in the first sequence. Copying the second sequence is the same with two replacing one and pos_two replacing pos_one. Only one of these last two loops will be entered since the first loop will be completed when one of the sequences has been completely processed. pos_one ← 0 pos_two ← 0 result ← [] while pos_one < length(one) and pos_two < length(two) if one[pos_one] < two[pos_two] result ← result + [one[pos_one]] pos_one ← pos_one + 1 else result ← result + [two[pos_two]] pos_two ← pos_two + 1 while pos_one < len(one) result ← result + [one[pos_one]] pos_one ← pos_one + 1 while pos_two < len(two) result ← result + [two[pos_two]] pos_two ← pos_two + 1