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 a Bubble 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.
Now comes time for our final program for this part of our tutorial. It
will be a bubble sort. I'll try to explain it as fully as possible.
First off, the bubble sort gets it's name from the way it sorts. It
compares two values and switches them if necessary. If you could
imagine a bubble in a soft drink floating up to the top, that's kinda
what this sort does. It is one of the slowest sorts ever developed.
On the upside, if the elements are already sorted, it is one of the
fastest, as it only goes through it once and then ends.
Anyway, here's the code:
/*------------------------------------------------------------------
Program: BSORT.C
Author: CORVUS
Date: Aug. 21, 2001
Description: This is a program that sorts an array of 10 integers
using the bubble 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, outer, inner; /* Loop counters */
int temp; /* temporary swap variable. */
for (i = 0; i < 10; i++) /* Display the unsorted array */
printf("%d\n",Num[i]); /* on the screen. */
/* Bubble Sort our array
from Biggest to Smallest */
for (outer=0; outer < 9; outer++) /* Loop while outer is */
for (inner=9; inner > outer; inner--) /* less than 9, (10 times) */
if (Num[inner-1] < Num[inner]) { /* and while inner is */
temp=Num[inner-1]; /* bigger than outer, */
Num[inner-1]=Num[inner]; /* execute "if" */
Num[inner]=temp;
}
/* print sorted array */
printf("\n");
printf("=====\n\n");
for (i=0; i < 10; i++)
printf("%d\n",Num[i]);
return 0;
}
Everything should look ok up until the Bubble Sort section itself.
We start with two "for" loops. When you have a loop inside another
loop, we call that nested. So what we have here 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). On the next line we have another "for" loop that counts
DOWN as long as inner is greater than outer. The next line is an "if"
statement. "if" statements are also new to you.
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. The rest of the program swaps values. What we are going
to do is walk through it using the values in our array, just as if the
program was running. We'll assume this is the first time though the
loops and we just reached the "if" statement. Here we go:
1. If Num[inner - 1] < Num[inner] translates to: if Num[8] < Num[9].
Well, since this is the first time through the loop, Num[8] = 1232 and
Num[9]=110. So the body of the "if" will not be executed because 1232
is NOT less than 110. The variable "inner" is now decremented by 1, and
we loop again.
2. if Num[inner - 1] < Num[inner] now translates to:
if Num[7] < Num[8].
We are now going through the inner loop a seconds time. Num[7] = 401
and Num[8] = 1232. This time we have: if 401 < 1232 which is TRUE
so the body of the "if" statement will now execute the sort algorithm.
The first line is: temp = Num[inner - 1] which translates into:
temp = Num[7].
What does that do? Well, it takes the value from Num[7], which is 401
and places that value into the variable called "temp". It is
interesting to note that this does not MOVE the value out of Num[7].
It merely copies it into temp. This means that "temp" and "Num[7]"
have equal value.
The second line is: Num[inner-1] = Num[inner] which translates to:
Num[7] = Num[8].
What does this line do? Well, it takes the value of Num[8] which is
1232 and copies it into Num[7]. This will replace the old value of
Num[7] which was 401, with 1232. Now "Num[7]" and "Num[8]" both hold
1232. Not for long though! Onto line 3.
The third line is Num[inner] = temp. This translates to: Num[8] = 401.
This simply gives "Num[8]" the value of 401, erasing the old value of
1232. Let's take a look at the arrays:
The original array Looked like this:
{234, 212, 0, 21, 14, 175, 998, 401, 1232, 110}
After the first time through the loop the "if" statement was FALSE so
it did not execute. Therefore nothing changed inside the array.
The second time through the loop the "if" statement was TRUE so it
executed the sort algorithm. The array now looks as follows:
{234, 212, 0, 21, 14, 175, 998, 1232, 401, 110}
I actually figured out the rest of the sort on paper and it took me
almost an hour. If you get bored you can try walking through it on
paper too. :-)
Anyway after the inner loop fails it's condition, you'll notice that
the values still aren't sorted. Hence the reason for the outer loop.
The array is guaranteed to be sorted after 10 times through through the
outer loop or less. In our case I think the values are sorted after
outer=6 and inner=9. But I'm not 100% sure about that. I kinda lost
count. You can step through it in a debugger and add a watch to the
variables "inner", "outer" and "Num".
On to Part 7.