Scope Top Input and LoopsLoops Contents

Loops

You can download the functions defined in this chapter with the following commands:

    wget troll.cs.ua.edu/ACP-C/loops.c
    wget troll.cs.ua.edu/ACP-C/loops.h
    wget troll.cs.ua.edu/ACP-C/scanner.c
    wget troll.cs.ua.edu/ACP-C/scanner.h

These files will help you run the test code listed in this chapter.

While loops

Loops are used to repeatedly execute some code. The most basic loop structure in C is the while loop, an example of which is:

    int i = 0;
    while (i < 10)
        {
        printf("%d\n",i);
        i = i + 1;
        }

We see a while loop looks much like an if statement. The difference is that blocks belonging to ifs are evaluated at most once whereas block associated with a loop may be evaluated many many times. Another difference in nomenclature is that the block of a loop is known as the body (like blocks associated with function definitions). Furthermore, the loop test expression is known as the loop condition.

As Computer Scientists hate to type extra characters if they can help it, you will often see:

    i = i + 1;

written three different ways:

    i += 1; 
    ++i;
    i++;

The latter two versions are read as "increment i" and saves at least a whopping two characters of typing, more as the variable name gets longer. The difference between the last and the second-to-last version is when the expression is used within a larger expression. Stylewise, this is generally a bad idea, so until you know better, always use ++i or i++ as stand-alone statements.

A while loop tests its condition before the body of the loop is executed. If the initial test fails, the body is not executed at all. For example:

    //test
    int i = 10;
    while (i < 10)
        {
        printf("%d\n",i);
        ++i;
        }
    printf("[nothing should have printed]\n");

never prints out anything since the test immediately fails. In this example, however:

    //test
    int i = 0;
    while (i < 10)
        {
        printf("%d",i);
        ++i;
        }
    printf("\n");
    printf("0123456789 should have printed\n");

the loop prints out the digits 0 through 9:

    0123456789

A while loop repeatedly evaluates its body as long as the loop condition remains true.

To write an infinite loop, use true as the condition:

    while (1)
        {
        i = getInput();
        printf("input is %d\n",i);
        process(i);
        }

The for loop

The other loop in C is the for loop:

    //test
    int i;
    for (i = 0; i < 10; ++i)
        {
        printf("%d\n",i);
        }

This loop is exactly equivalent to:

    //test
    int i = 0;
    while (i < 10)
        {
        printf("%d\n",i);
        ++i;
        }

In fact, a while loop of the general form:

    i = INIT;
    while (i < LIMIT)
        {
        // body
        ...
        i += STEP;
        }

can be written as for loop:

    for (i = INIT; i < LIMIT; i += STEP)
        {
        // body
        ...
        }

For loops are commonly used to sweep through each element of an array:

    //test
    int i;
    int items[] = { 0,1,1,2,3,5,8,13 };
    int itemCount = sizeof(items)/sizeof(int);

    for (i = 0; i < itemCount; ++i)
        {
        printf("%d\n",items[i]);
        }

Here, we sweep through an array of integers. Since we cannot tell, in general, the size of the array given the name of the array, we must make available the size of the size of the array to the loop. In the example above, the size of the array is stored in the variable itemCount.

Recall the items in an array of n elements are located at indices 0 through n - 1. These are exactly the values produced by the initialization, test, and step of the for loop. The above loop accesses each element by its index in turn, and thus prints out each element, in turn. Since using an index of n in an array of n items produces an error, the test of the index i against the size of the array uses a strict "less than" comparison.

A common use for loops is to initialize an array. Recall that when an array is allocated statically without initializers or is dynamically allocated, the slots are filled with garbage. A loop can be used to set the elements of an array to a known value:

    array = malloc(sizeof(int) * size);
    //check for malloc failure omitted
    for (i = 0; i < size; ++i)
        {
        array[i] = 0;
        }

Loops and arrays go very well together; the next sections detail some common loop patterns involving arrays.

The counting pattern

The counting pattern is used to count the number of items in a collection. Note that we require the size of the array to be available, so counting the elements in an array is a bit of a waste of time. Still, it is about the easiest array processing loop to write, so let's forge ahead29

    int i,count = 0;
    for (i = 0; i < itemCount; ++i)
         {
         ++count;
         }
    //count now holds the number of items

When the loop finishes, the variable count holds the number of items in the array. In general, the counting pattern increments a counter every time the loop body is evaluated.

The counting pattern is more useful for while loops. Suppose we are trying to count the number of characters in a file. Suppose further that the function getNextCharacter reads and returns the next character in a file or it returns -1 if there are no more characters to be read. A counting loop would look like this:

    count = 0;
    ch = getNextCharacter();
    while (ch != -1)
        {
        ++count;
        ch = getNextCharacter();
        }
    //count now holds the number of characters

At the end of the loop, count holds the number of characters in the file. Note how we did not need to know the number of characters in advance. The reason is we had a way to detect when the counting loop should stop running.

The filtered-count pattern

A variation on the counting pattern involves filtering. When filtering, we use an if statement to decide whether we should count an item or not. Suppose we wish to count the number of even items in an array:

    int i,count = 0;
    for (i = 0; i < itemCount; ++i)
        {
        if (items[i] % 2 == 0)  //true if items[i] is even
            {
            ++count;
            }
        }
    //count now holds the number of even items

When this loop terminates, the variable count will hold the number of even integers in the array of items. The if makes sure the count is incremented only when the item of interest is even.

The accumulate pattern

Similar to the counting pattern, the accumulate pattern updates a variable, not by increasing its value by one, but by the value of an item. This loop, sums all the values in an array:

    int i,total = 0;
    for (i = 0; i < itemCount; ++i)
        {
        total += items[i];      //equivalent to total = total + items[i];
        }
    //total now holds the sum of all items

By convention, the variable total is used to accumulate the item values. When accumulating a sum, the total is initialized to zero. When accumulating a product, the total is initialized to one30.

The filtered-accumulate pattern

Similar to both the filtered-count pattern, the filtered-accumulate pattern updating the total only if some test is passed. This function sums all the even values in a given array, returning the final sum:

    int
    sumEvens(int *items,int itemCount)
        {
        int i,total;
        total = 0;
        for (i = 0; i < itemCount; ++i)
            {
            if (items[i] % 2 == 0)
                {
                total += items[i];
                }
            }
        return total;
        }

As before, the variable total is used to accumulate the item values. As with a regular accumulating, total is initialized to zero when accumulating a sum. The initialization value is one when accumulating a product and the initialization value is the empty array when accumulating an array (see filtering below).

The search pattern

The search pattern is a slight variation of filtered-counting. Suppose we wish to see if a value is present in an array. We can use a filtered-counting approach; if the count is greater than zero, we know that the item was indeed in the array.

    int
    occurrences(int target,int *items,int itemCount)
        {
        int i,count;
        count = 0;
        for (i = 0; i < itemCount; ++i)
            {
            if (items[i] == target)
                {
                ++count;
                }
            }
        return count;
        }

    int
    find(int target,int *items,int itemCount) // is target in items?
        {
        return occurrences(target,items,itemCount) > 0;
        }

In this case, occurrences implements the filtered-count pattern and helps find do its job. We designate such functions as occurrences and the like, helper functions. However, we can improve the efficiency of find by having it partially implement the filtered-count, but short-circuiting the search once the target item is found. We do this by returning from the body of the loop:

    int
    find(int target,int *items,int itemCount)
        {
        int i;
        for (i = 0; i < itemCount; ++i)
            {
            if (items[i] == target)
                {
                return 1;             // short-circuit! return true
                }
            }
        return 0;   //must not be in the array, return false
        }

When the array is empty, we return false, as indicated by the last line of the function, because the loop never runs and thus the return inside the loop can never be reached. In the same vein, if no item matches the target, we cannot return true, and eventually the loop exits and false is returned.

As a beginning programmer, however, you should be wary of returning from the body of a loop. The reason is most beginners end up defining the function this way instead:

    int
    find(int target,int *items,int itemCount)
        {
        int i;
        for (i = 0; i < itemCount; ++i)
            {
            if (items[i] == target)
                return 1;
            else
                return 0;
            }
        }

The first problem with this definition is that the compiler generates a warning indicating that it is possible for the function to complete without explicitly returning a value. The second problems is that the function fails to find the target most times. Unfortunately, it works correctly under some conditions, which is why thorough testing of code is always a good thing. If you cannot figure out why this version generates the warning and why it fails under some conditions but succeeds under others, you most definitely should stay away from placing returns in loop bodies.

The extreme pattern

Often, we wish to find the largest or smallest value in an array. Here is one approach, which assumes that the first item is the largest and then corrects that assumption if need be:

    int i,largest = items[0];
    for (i = 0; i < itemCount; ++i)
        {
        if (items[i] > largest)
            {
            largest = items[i];
            }
        }
    //largest now holds the largest item

When this loop terminates, the variable largest holds the largest value. We can improve the loop slightly by noting that the first time the loop body evaluates, we compare the putative largest value against itself, which is a worthless endeavor. To fix this, we can start the index variable i at 1 instead:

    int i,largest = items[0];
    for (i = 1; i < itemCount; ++i) //start comparing at index 1
        {
        if (items[i] > largest)
            {
            largest = items[i];
            }
        }
    //largest now holds the largest item

Novice programmers often make the mistake of initialing setting largest to zero and then comparing all values against largest, as in:

    int i,largest = 0;
    for (i = 0; i < itemCount; ++i)
        {
        if (items[i] > largest)
            {
            largest = items[i];
            }
        }
    //largest may hold an incorrect value!

This code appears to work in some cases, namely if the largest value in the array is greater than or equal to zero. If not, as is the case when all values in the array are negative, the code produces an spurious result of zero as the largest value.

The extreme-index pattern

Sometimes, we wish to find the index of the most extreme value in an array rather than the actual extreme value. In such cases, we assume index zero holds the extreme value:

    int i,ilargest = 0;
    for (i = 0; i < itemCount; ++i)
        {
        if (items[i] > items[ilargest])
            {
            ilargest = i;
            }
        }

Here, we successively store the index of the largest value seen so far in the variable ilargest.

The filter pattern

A special case of a filtered-accumulation is called filter. Instead of summing the filtered items (for example), we keep the filtered items in the array. The modified array is said to be a reduction of the original array.

Suppose we wish to remove the odd numbers from an array. The code looks very much like the sumEvens function, but instead of adding in the desired item, we move the even numbers to the front of the array, overwriting any odd numbers or any previously moved even items.

    int
    removeOdds(int *items,int itemCount)
        {
        int i,j;
        j = 0;
        for (i = 0; i < itemCount; ++i)
            if (isEven(items[i]))
                {
                items[j] = items[i];
                ++j;
                }
        return j;
        }

The removeOdds function needs to implement the function pattern, because we need to return the number of items that were kept in the array. This number becomes the new size of the array. The caller of the removeOdds function is responsible for updating the size of the array:

     int data[] = {1,2,3,4,5,6};
     int size = sizeof(data) / sizeof(int);
     size = removeOdds(data,size);

Here is a pictorial view of the workings of removeOdds. Suppose we start with items pointing to this array:

Both i and j start at zero, so they have been placed above and below slot 0. The brackets around the variables are to remind us these variables are used as indices into the array. When the first element is checked, we see that it is odd. We drop to the bottom of the loop and increment i, leaving us at:

Now, we check the element at index i and we see it is even. We copy it to the slot at index j, overwriting the 5 that was there originally:

We then increment j and then, at the bottom of the loop, increment i. Now the situation is:

Again, the element at index i is even, so we copy it to slot j. We then increment both i and j:

The element at i is odd, so we simply increment i for this iteration of the loop:

Now the element at i is even, so we copy it to slot j. After incrementing both j and i, we have:

At this point, i is equal to itemCounts, the loop ends, and we return j as the new size of the array. In the example, j has a value of 3. This is as desired, as there were three even numbers in the original array.

Of course, we are being a bit wasteful here, in that there may be unused slots at the end of the array. You will note that 1 and 6 remain in the array, but they have no effect because the caller of removeOdds will believe the array has shrunk, assuming the caller properly resets the size of the array:

    //test (compile with loops.c)
    #include "loops.h"

    int i;
    int a[] = {5,2,4,1,6};
    int aSize  = sizeof(a) / sizeof(int);

    aSize = removeOdds(a,aSize);

    for (i = 0; i < aSize; ++i)
        {
        printf("[%d]",a[i]);
        }
    printf("\n");

This code should print out:

    [2][4][6]

as desired. Since the original array is modified, we say that removeOdds is a destructive procedure. We might also say the removeOdds implements a destructive filtering pattern.

If removeOdds instead allocated a new array to store the even numbers, filled that array with the even numbers found in items, and returned the newly allocated and filled array, then removeOdds would implement a non-destructive filtering pattern:

    int
    removeOdds2(int *items,int itemCount,int *evens) //non-destructive
        {
        int i,j;
        j = 0;
        for (i = 0; i < itemCount; ++i)
            if (isEven(items[i]))
                {
                evens[j] = items[i];
                ++j;
                }
        return j;
        }

In this version, we are required to pass in an array to hold the even values:

    //test (compile with loops.c)
    #include "loops.h"
    int i;
    int a[] = { 5, 2, 4, 1, 6 };
    int aSize = sizeof(a) / sizeof(int);
    int b[] = { 0, 0, 0, 0, 0 };
    int bSize = sizeof(b) / sizeof(int);

    bSize = removeOdds2(a,aSize,b);

    for (i = 0; i < bSize; ++i)
        printf("[%d]",b[i]);
    printf("\n");

Of course, the caller must ensure that the array b is large enough to hold all the even values in a. Most often, the array b would be allocated dynamically, rather than statically:

    ...
    int *b = (int *) malloc(sizeof(int) * aSize);
    //the test that malloc succeeded omitted
    int bSize = aSize;

    bSize = removeOdds2(a,aSize,b);
    ...
    free(b);

Rather than call malloc and then check if the allocation succeeded, we can write a wrapper function that does the allocation and checking:

    char *
    allocate(int size)
        {
        char *s = malloc(size); //size given in bytes
        if (s == 0)
            {
            fprintf(stdin,"allocate: out of memory\n");
            exit(1);
            }
        return s;
        }

Now we can use allocate instead of malloc, obviating the need for us to write the allocation checking code. You can find a version of allocate in the scanner.c file. The code fragment above becomes:

    ...
    int *b = (int *) allocate(sizeof(int) * aSize);
    int bSize = aSize;

    bSize = removeOdds(a,aSize,b);
    ...
    free(b);

From here on out, we will use allocate instead of malloc. You would need to include the definition of allocate in your code if you wish to use it in your programming.

The map pattern

Mapping is a task closely coupled with that of filtering, but rather than collecting certain items, as with the filter pattern, we collect all the items. As we collect, however, we transform each item as we collect it, using a passed in function. The basic destructive pattern looks like this, with the formal parameter f holding the function used to transform the original items:

    void
    map(int *items,int itemCount,int (*f)(int)) //destructive
        {
        int i;
        for (i = 0; i < itemCount; ++i)
            items[i] = f(items[i]);      //pass items[i] through function f
        }

The type of the formal parameter f looks rather odd. Recall, from the last section of the chapter More about Functions, how we derive the type of a variable that can point to a function. Let's review with the square function, whose definition is:

    int square(int x) { return x * x; } //definition

and whose signature is:

    int square(int);                    //signature

First, we wrap the name of the function in the function signature with parentheses:

    int (square)(int)

Then we place an star in front of the function name (inside the parentheses we just added):

    int (*square)(int)

Finally, substitute the formal parameter name for square:

    int (*f)(int)

The formal paramter f has type int (*)(int).

So any time you wish to pass a function to another function, you can follow this technique to derive the type of the formal parameter that receives the passed-in function.

Suppose we wish to subtract one from each element in an array. First we need a transforming function that reduces its argument by one:

    int decrement(int);                     //signature
    ...
    int decrement(int x) { return x - 1; }  //definition

Now we can "map" the decrement function over an array of numbers:

    //test (compile with loops.c)
    #include "loops.h"
    int i;
    int a[] = { 5, 2, 4, 1, 6 };
    int aSize = sizeof(a) / sizeof(int);

    map(a,aSize,decrement);

    for (i = 0; i < aSize; ++i)
        printf("[%d]",a[i]);
    printf("\n");

For output, we get:

    [4][1][3][0][5]

as expected.

A non-destructive version of map is similar to the non-destructive version of filter; we need to pass in the accepting array:

    void
    map2(int *items,int itemCount,int (*f)(int),int *mapped) //non-destructive
        {
        int i;
        for (i = 0; i < itemCount; ++i)
            mapped[i] = f(items[i]);      //pass items[i] through function f
        }

The array mapped should be the same size as the array items.

The append pattern

Sometimes, we wish to create a third array that contains the elements of two arrays. The append pattern, places the elements of second array after the elements of the first array with all elements placed in the third array:

     ...
     //a and b are integer arrays with sizes aSize and bSize
     cSize = aSize + bSize;
     c = (int *) allocate(cSize * sizeof(int));

     append(a,aSize,b,bSize,c);

The definition of append might look like this:

    void
    append(int *a,int aSize,int *b,int bSize,int *c)
        {
        int i,spot;
        spot = 0;
        for (i = 0; i < aSize; ++i)
            {
            c[spot] = a[i];
            ++spot;
            }
        for (i = 0; i < bSize; ++i)
            {
            c[spot] = b[i];
            ++spot;
            }
        //c now holds all of a and b
        }

We use index i to walk through the source arrays a and b and the index spot to keep track of where we are in the destination array c.

The shuffle pattern

When we wish to combine two arrays into a third array, sometimes we wish to shuffle the items in the source arrays, much like shuffling a deck of cards, rather than appending them.

Here is one attempt. The shuffle function places the items from the first source array in the even locations of the destination array. Likewise, it places items from the second source into the odd locations:

    int *
    shuffle(int *a,int aSize,int *b,int bSize)
        {
        int *c; //a pointer to the destination array
        int i,spot;
        
        c = malloc(sizeof(int) * (aSize+bSize)); //malloc failure test omitted

        spot = 0;                       //the first even slot
        for (i = 0; i < aSize; ++i)
            {
            c[spot] = a[i];
            spot += 2;                  //skip to the next even slot
            }
        spot = 1;
        for (i = 0; i < bSize; ++i)     //the first odd slot
            {
            c[spot] = b[i];
            spot += 2;                  //skip to the next odd slot
            }
        //c now holds all of a and b
        return c;
        }

Note that this first version only works if the source arrays are the same size. Suppose the first source has the elements 3, 8, 2, 4, and 5, while the second has the elements 7, 1, and 6. After placing the first source, the destination arrays looks like this:

The question marks signify holes in the array. These holes are slots that have not been explicitly filled and thus contain garbage, due to the way C dynamically allocates arrays. After adding in the second source, we have:

Note that holes remain at the end of the destination array. There is a worse problem, however. Presumably, the destination array was allocated to be just big enough to hold the all the elements in the source arrays. In our example, that would be a size of 8. However, the last element placed, the 5, was placed at index 8, which would be beyond the extent of the destination array. It is clear, for mismatched source arrays, we need a better solution.

Here is one approach: we shuffle the two arrays, as before, but stop when we run out of items in one of the source arrays. We then fill out the remainder of the destination array with the unused elements in the other source array.

To implement this second approach, we will combine the two loops from the first attempt at shuffle, but limit the loop's run to the smaller of the two source array sizes:

    spot = 0;
    for (i = 0; i < aSize && i < bSize; ++i)
        {
        c[spot] = a[i];     //spot must be even here
        c[spot+1] = b[i];   //spot+1 therefore must be odd
        spot += 2;
        }

After this loop runs, our destination array looks like:

with spot referencing the slot of the first question mark. The variable i, on the other hand, holds the index of the next element that should go into the destination array. We don't know which, so we will attempt to copy elements from both sources:

    while (i < aSize)
        {
        c[spot] = a[i];
        ++spot;
        ++i;
        }

    while (i < bSize)
        {
        c[spot] = b[i];
        ++spot;
        ++i;
        }

How can this possibly work when one of the sources is all used up? Suppose the first source is exhausted. We know that i must be equal to aSize in that case. Therefore, the first while loop test immediately fails and the loop body is never executed. We continue on to the next loop, where i must hold the index of first unused element in the second source. We continue to copy elements over into the destination array until the source is exhausted.

Conversely, if the for loop ends with the second source exhausted, we copy over elements from the first source. At this point, the variable i is greater than the size of the second source, so the second while loop immediately fails. In either case, the destination array holds all the elements of the source arrays with the elements shuffled as much as possible. Putting it all together yields the following implementation for shuffle:

    int *
    shuffle(int *a,int aSize,int *b,int bSize)
        {
        int *c; //a pointer to the destination array
        int i,spot;
        
        c = malloc(sizeof(int) * (aSize+bSize)); //malloc failure test omitted

        //shuffle until one source is exhausted
        spot = 0;
        for (i = 0; i < aSize && i < bSize; ++i)
            {
            c[spot] = a[i];     //spot must be even here
            c[spot+1] = b[i];   //spot+1 therefore must be odd
            spot += 2;
            }

        //i is either equal to aSize or bSize
        //spot holds the index of the 1st available slot in c

        // copy over leftover elements in a, if any
        while (i < aSize)
            {
            c[spot] = a[i];
            ++spot;
            ++i;
            }

        // copy over leftover elements in b, if any
        while (i < bSize)
            {
            c[spot] = b[i];
            ++spot;
            ++i;
            }

        //c now holds the shuffle of a and b
        return c;
        }

With this new version, what happens when the sizes of the source arrays are equal? The superior student will quickly ascertain the validity of the new version in this case.

One last note: the three pieces of a for loop, INIT, LIMIT, and STEP, are all optional. We could replace the first while loop with this for loop:

        for ( ; i < aSize; ++i) //i starts at its previous value
            {
            c[spot] = a[i];
            ++spot;
            }

The second while loop could be replaced in a similar fashion.

The merge pattern

With the shuffle pattern, we always took the head elements from both arrays at each step in the shuffling process. Sometimes, we wish to place a constraint of the choice of elements. For example, suppose the two arrays to be combined are sorted and we wish the resulting array to be sorted as well. The following example shows that shuffling does not always work:

    //test (compile with scanner.c and loops.c)
    #include "scanner.h"
    #include "loops.h"

    int i;
    int a[] = {1,4,6,7,8};   //a is sorted
    int b[] = {2,3,9};       //b is sorted
    int *c;
    int aSize,bSize,cSize;

    aSize = sizeof(a) / sizeof(int);
    bSize = sizeof(b) / sizeof(int);

    c = shuffle(a,aSize,b,bSize);
    cSize = aSize + bSize;

    for (i = 0; i < cSize; ++i)
        printf("[%d]",c[i]);
    printf("\n");

Running this code gives us the following output:

    [1][2][4][3][6][9][7][8]

Clearly, the destination array c is not sorted.

The merge pattern is used to ensure the resulting array is sorted and is based upon the filtered-accumulate pattern. The twist is we only accumulate an item if it is the smallest item in the two arrays that has not already been accumulated. We start by keeping two index variables, one pointing to the smallest element in the first source and one pointing to the smallest element in second source. Now, we loop, similar to shuffle. The difference is we will only advance the index variable of a source array if we use the smallest of its unused elements:

    i = 0;          //index of the smallest unused element in a
    j = 0;          //index of the smallest unused element in b
    spot = 0;
    while (i < aSize && j < bSize)
        {
        if (a[i] < b[j])    //a's element is smaller, use it
            {
            c[spot] = a[i];
            spot++;
            i++;
            }
        else                //b's element is smaller, use it
            {
            c[spot] = b[j];
            spot++;
            j++;
            }
        }

Inside the loop, we test to see if the smallest unused element in a is smaller than the smallest unused element in b. If it is, we copy the element from a to c and increment a's index variable, "using up" the smallest unused value. Likewise, we do the same for b if b's element is smaller.

The while loop ends when one of the source arrays is exhausted. At this point, we just copy over the elements in the unexhausted source, just the same as we did for shuffle. Putting it all together yields:

    int *
    merge(int *a,int aSize,int *b,int bSize)
        {
        int *c; //a pointer to the destination array
        int i,j,spot;
        
        c = malloc(sizeof(int) * (aSize+bSize)); //malloc failure test omitted

        //merge until one source is exhausted
        spot = 0;
        for (i = 0,j = 0; i < aSize && j < bSize; ++spot)
            {
            if (a[i] < b[j])    //a's element is smaller, use it
                {
                c[spot] = a[i];
                i++;
                }
            else                //b's element is smaller, use it
                {
                c[spot] = b[j];
                j++;
                }
            }

        //i is either equal to aSize or j is equal to bSize
        //spot holds the index of the 1st available slot in c

        // copy over leftover elements in a, if any
        for ( ; i < aSize; ++i)
            {
            c[spot] = a[i];
            ++spot;
            }

        // copy over leftover elements in b, if any
        for ( ; j < bSize; ++j)
            {
            c[spot] = b[j];
            ++spot;
            }

        //c now holds the shuffle of a and b
        }

The main while loop has been rewritten as a for loop by taking advantage of for loop flexibility. Note we can initialize two (or more) variables in the INIT portion of the loop by separating the initializations with a comma. We also moved the increment of spot to the STEP portion since we increment spot regardless of the which array held the smaller value. We do not want to increment i and j in the STEP portion since those indices only get incremented when their arrays hold the smallest unused elements.

The fossilized pattern

Sometimes, a loop is so ill-specified that it never ends. This is known as an infinite loop. Of the two loops we are investigating, the while loop is the most susceptible to infinite loop errors. One common mistake is the fossilized pattern, in which the index variable never changes so that the loop condition never becomes false:

    i = 0;
    while (i < n)
        {
        printf("%d\n",i);
        }

This loop keeps printing until you terminate the program with prejudice. The reason is because i never changes; presumably a statement to increment i at the bottom of the loop body has been omitted.

The missed-condition pattern

With the missed condition pattern, the index variable is updated, but it is updated in such a way that the loop condition never evaluates to false.

    i = getAnInteger();
    while (i != 0)
        {
        printf("%d\n",i);
        i -= 2;
        }

If the getAnInteger returns a positive, even number, then the loop terminates as expected. However, if getAnInteger returns an odd or negative number, the loop never ends. Suppose i starts out with the value 5. The loop test keeps succeeding and the value of i keeps being printed:

    5
    3
    1
    -1
    -3
    -5
    -7
    ...

Here, the variable i has skipped over the value used for terminating the loop; i never becomes zero. Thus, the loop condition never fails and the loop becomes infinite.

lusth@cs.ua.edu


Scope Top Input and LoopsLoops Contents