Part 6
------
This section will be a little larger than the last two. In this
section we will discuss Arrays, as well as the "for" loop. Maybe
I'll throw in a sorting algorithm. A simple one called an Insert Sort.
I found the following definition of an array (I can't remember where):
An array is a structured collection of components (often called
elements) of the same type, that is given a single name. Each array
element is accessed by an index that indicates the elements position
within the collection.
Let's look at an example of how to declare an array:
int Num[1000];
The above statement declares Num to be an array of 1000 elements of
type int. That means that we have just reserved enough space
somewhere in memory for 1000 integer values. This is a lot easier
than writing a program with 1000 individual variables.
The first element has an Index value of 0, the seconds has an index
value of 1, and the last element has an index value of 999.
You might now be wondering what we can do with 1000 integer values. :-)
Well, we can sort them! Before I show you how to sort them, let's go
over the semantics of the "for" loop.
A "for" statement has the following structure:
for (InitStatement; Condition; Expression)
Statement;
Let's take a look at a program that uses a for loop.
/*-------------------------------------------
This program prints out numbers from 0 to 20
------------------------------------------*/
#include <stdio.h>
int main(void)
{
int count;
for (count = 0; count <= 20; count++)
printf("%d\n", count);
return 0;
}
I remember when I first saw a for loop. I stopped learning C and went
back to Pascal. Just kidding. At first glance it may seem slightly
obscure. Allow me to walk you through it.
The for statement in our program translates to:
Set the loop control variable "count" to 0. While "count" is less than
OR equal to 20, jump to the "printf" statement to display output, then
jump back to increment "count" by 1.
The program will stop after "count" has been incremented to 20 + 1;
All for loops operate in approximately this way.
You can also count down by setting our "count" variable to 20, change
our condition to check if count >= 1 and then decrement our counter
by using count--.
By the way "count = count + 1" is the same as "count++".
Also "count = count - 1" is equal to "count--".
Now that you know how to use arrays and a loop construct, we'll use
both together. We will rewrite the above program to use arrays in
the "for" loop.
/*-----------------------------------------------
This program prints out numbers from 0 to 20
using an array to hold the 21 values.
----------------------------------------------*/
#include <stdio.h>
int main(void)
{
int count[21];
int i;
for (i = 0; i<21; i++)
count[i] = i; /* Fill count[] with 21 values (0 - 20) */
for (i = 0; i<21; i++)
printf("Count[%d] = %d\n", i, count[i]); /* Display count[] */
return 0;
}
We make an array of 21 because we want to display values from 0 - 20.
If we made the array only 20 elements in size it would only print 0 - 19.
The last item to discuss is the "if" statement:
An "if" statement is used for comparing items. For example:
int X = 9
int Y = -2
if (X > Y)
printf("X is Bigger.\n");
Easy eh? :-) It can get very complicated at times, but I doubt I'll
cover that.
Now comes time for our final program for this part of our tutorial. It
will be an insert sort. I'll try to explain it as fully as possible.
Here's the code:
/*------------------------------------------------------------------
Program: INSORT.C
Author: CORVUS
Date: Sept. 17, 2001
Description: This is a program that sorts an array of 10 integers
using the Insert sort algorithm.
------------------------------------------------------------------*/
#include <stdio.h>
int main(void)
{
/* Initialize our array */
int Num[10] = {234, 212, 0, 21, 14, 175, 998, 401, 1232,110};
int i; /* Loop counter for displaying results */
int outer, inner;
int tmp;
/* Display the unsorted array
on the screen. */
for (i = 0; i < 10; i++)
printf("%d\n", Num[i]);
/* Do Insert Sort */
for (outer = 1; outer < 10; outer++) /* look for insertion point. */
for (inner = outer; (inner > 0) && (Num[inner - 1] > Num[inner]); inner--) {
/* Move the others down and insert it. */
tmp = Num[inner];
Num[inner] = Num[inner - 1];
Num[inner - 1] = tmp;
}
/* print sorted array */
printf("\n");
printf("=====\n\n");
for (i = 0; i < 10; i++)
printf("%d\n", Num[i]);
return 0;
}
We will run through the sort as if it were the first time through the
loops.
Everything should look ok up until the Insert Sort section itself.
We start with two loops. The two loops are "for" loops. When you have
a loop inside another loop, we call that nested loops. So what we have
here is are nested "for" loops. The first "for" loop we encounter
simply loops 10 times. It loops 10 times because that's how many items
we have in the array (Remember that arrays start at 0 in C...Not at 1,
so 0..9 is 10 elements).
The following line is our second "for" loop. This loop first sets
"inner" equal to "outer". This would be translated in our program to:
"inner = 1" (assuming it's our first time through the loop). After it
does that, it does the test. The test is:
"(inner > 0) && (Num[inner - 1] > Num[inner])". Let's assume this is
the first time through the loop. We'll replace the variables with
numbers, just like the program would when it is running. Here we go:
"(inner > 0)" = "(1 > 0)". This is true, so we continue on to the
other test: "(Num[inner - 1] > Num[inner])" = "(Num[0] > Num[1])",
which can be broken down even further to: "(234 > 212)" which is true.
So, when we piece the line together it says "if(1 > 0) and (234 > 212)"
then execute the body of the loop. Well, on our first run through, we
see that the body of the inner "for" loop will be executed. Let's take
a look at that part now.
The first line following the loop is: "tmp = Num[inner]". We know that
"Num[inner] = 212". We also know that it is in the second element of
the array. Since the first element is bigger than the second, we are
going to swap them. We need another variable to swap the values to, so
as not to overwrite them. That is why we have a "tmp" variable. We
are storing the value of "Num[1]" into "tmp". Because "Num[1]" = 212,
"tmp" now also equals 212.
The next line is: "Num[inner] = Num[inner - 1]". This takes the value
of "Num[0]" and places it into "Num[1]", effectively overwriting its
previous contents (hence the reason for our "tmp" variable).
The next line is: "Num[inner - 1] = tmp". This takes the value of
"tmp", which is 212 and places it in "Num[0]", overwriting the previous
value of 234. The array now looks like this:
{212, 234, 0, 21, 14, 175, 998, 401, 1232, 110}
Anyway, after the body is completed, we jump back into the "for" loop
and decrement "inner" with "inner--". The value of "inner" is now 0.
After it does that, it jumps back to the test condition, which because
"inner" is now 0 reads as: "(0 > 0)". It stops at this point because
zero is not bigger than 0. There is no need to go any farther. We
then exit out of our inner loop and go back to the final statement in
our outer loop, which is "outer++". We increment outer by 1. We then
execute the test inside the for loop that reads: "outer < 10". Simply
put, if outer is less than 10, go to the next line. The value of
"outer" is now 2. 2 is less than 10. so we go back into our inner loop.
I recommend you try to continue walking through it either by hand, like
we just did or with a debugger. I find that when I use a debugging
program, I tend to spot errors fairly quickly and sometimes understand
what's going on a little bit better. Just be careful that you pay
close attention. A debugging program won't help you if you don't watch
the output it is giving you. Pay attention and you might catch bugs
didn't expect.
We will now move to Part 7.