Tip:
Highlight text to annotate it
X
In this lesson we're gonna see how we can work with arrays. We're gonna do a lot of traversals and this is going to point out
a very important fact about arrays. Again, the memory is contiguous which means we can index through
the data and what is most suited for this, of course is a loop and a counting loop. The four statement. You'll see
the for statement being used multiple times to traverse arrays for various tasks. We're going to began with a traversal simply to read in
some information from users. We've declared a constant "size",
to be five, an array of "ages" of size five and initialize them all to zero. We have a sum, an average we set to zero and then a for loop
that's going to traverse the array. Now, again remember that the indices on the array run from
zero to "size" -1.This is extremely important! Look at the for loop.
We start our index at zero and go up to, but not including "size". This is extremely important. And, again
I want to point out the utility of declaring that "size" is a constant. Suppose that I don't have five people but 50 people I can change it in one spot
and everything changes the declaration and the traversal changed
and no other change has to take place. It's very simple.
Let's run through this. With "i" equal to zero, I'm going to look at the 0th
element. I will prompt for and to enter an age for the first person. That is going to be 12.
Increment to one, read in 15, increment to two: 31, increment to three: 18, increment to four and enter 14.
So I've run through the array completely, from "i" equal to zero to "i" equal to four, which is less than size.
As soon as I go up to five, I'm no longer less than size and I'm out of that loop. Second traversal, same array, again a for loop, I'm going to go from
zero up to, but not including "size" is extremely important, so I'm traversing the array from the 0th the 4th element,
I'm going to sum up the ages. So, for "i" equal to zero, I have sum is zero. I'm gonna add in 12, add in 15, add in 31, add in
18, add in 14, and my sum is 90 and I calculate the average to be
90 divided by 5 is 18, and output that.
For our third traversal, I'm going to find the maximum value in the array. What I'll do is,
I'm gonna write this code to emulate the way I would do it if I was a human being.
And this is what you wanna do quite often with your code.
Take a look at what you do. Remember what we did in the first lesson? We looked at algorithms.
If I give you this array and ask you, find the maximum value,
what do you do? Well, you look at the first elements and say, this is the biggest one so far and hold on that, you look at the second,
15 okay, that's bigger, I'm going to replace that 12. 31. Ah, that's bigger, that's now the biggest one. 18, no, that's not bigger. 14, no that's not bigger.
31 that was the biggest one I remember. What you did was you held on to each item as you went and if you found something that was bigger,
you replaced it. That is exactly what your code is going to do. You have to slow down your thinking process and write code that emulates that
process. So, look at our for statement here. We're gonna start at "i" equal to 1 now. Why 1? Well, because I set my maximum to be
ages zero. The very first element, I don't need to look at it. So I'm going to start at one, and go up to, but not including "size" again.
If I went up to & included "size", then I'd be looking at memory out here that that's not mine. So, for "i" equal to 1, is "ages[1]" bigger than "max"?
Yes it is, so I'm going to assign it to "max". Increment to 2. I ask the question: is it bigger? Yes, so assign it.
To 3. Is "ages[3]" bigger than "max"? The answer is, no. Go to 4, is it bigger? No, and I'm done. I output
what the max of the array is.
For our next traversal of this very same array, I'm going to sort it.
This is actually a coding of the sorting algorithm we know as bubble sort.
Alright? It is a loop inside of a loop. A for loop inside of a for loop. The outer loop
names how many times I'm actually going to traverse the data. The inner loop
is going to do the work. So for each "j" I'm gonna ask
is "ages[j]" bigger than "ages[j+1]"? I'm gonna compare the very first two elements. Is 12 bigger than 15? If it is, I'm gonna swap it.
That's what the code below is. If it's not, I'm going to leave it alone. It's not, so I'm going to increment "j" up to 1 and look at "ages[j]" and "[j+1]".
So, is 15 bigger than 31? No. I increment to "j"=2. Ask the question, is "ages[2]" bigger than "ages[3]"? The answer is yes, so I need to swap
these two values. 31 goes up, 18 goes back. I declare a temporary variable called swap, I'm going to assign it 31,
I'm going to assign 18 to "ages[2]" and then I'm going to move that swap into "ages[3]".
So, I've held on, temporarily, to the lower value, moved the higher value in and then assign that lower value up.
Okay, increment "j" to 3, ask the question: is "ages[3]" bigger than "ages[4]"? It is, so I'm going to swap. Create the temporary variable,
move that one down, move it in and we're swapped. "j" is 4, that is now no longer less than "size" - "i", "i" being one. And so, I'm ready to
move on. I'm going to increment "i" to 2, so this it the second traversal. I'm going to do everything again.
What have I accomplished so far? So far the largest value is at the top of
the dataset. This is why it is called a bubble sort.
I'm going to look at this data next, and then I'm going to look at these, and then I'm going to look at these, then last but not least, that.
That's the outline of what happens. So for "i" = 2, again "j" is 0, is
"ages[0]" bigger than "ages[1]"? No.
Move up. Is 15 bigger than 18? No, move up. Is 18 bigger than 14? Yes, so I'm going to swap them.
Now "j" is 3.
and I'm done. I'm going to increment "i" to three, and look at only these values. Again,
I ask, is 12 bigger than 15? No.
Next: is 15 bigger than 14? Yes, so I will swap.
And then "j" is two, and I'm done with that iteration.
Increment "i" to 4, "j" = 0, is 12 bigger than 14? The answer is no. Increment "j" to 1 and I'm done. Increment "i" to five and I am done. And this
is bubble sort. Okay, how do we send arrays to functions? Arrays as parameters?
There are several points to be made here. If you wanna send an array to a function, then I guess the very first thing I would think about is
this is a print array function. All it's going to do is print the array, so I want to put a constant on that variable.
I'm not going to change the array, so make it a constant.
Alright, in this case, it's gonna be an array of floats,
I'm going to call the parameter "the_array" and in order to tell the compiler
that it is an array, that it is to be expected here. I've gotta put that open and closed brackets. Do you put anything in the brackets?
No, nothing should go in the brackets. You might think, "shouldn't I put the size of the array?" But, that doesn't make sense because that would
imply that this function only works for arrays of a particular size. And that is pretty useless.
So, you just put brackets. And, incidentally if you put something in the brackets, the compiler will ignore it.
Quite often, when you send an array to a function,
then you need to send the size of the array also. And of course, that would be declared "const" and "int" and "size". That the gives information
to the function, how to traverse. How many elements are in the array and so how to traverse all of the data. The code inside the function is a
Here in my main, I've declared an array called "my_array" of size "size", which is a constant declared to be 100.
So, I'm going to call "print_array", I send to it "my array". Now how do I do that?
All I have to do is name "the_array".
Okay? You do not want to put brackets there.
See, it's really a bad thing. You get the big red arrow. Let's do this again to make sure you understand.
Do not put those brackets in there. Okay? And of course, we're going to send "size".
Moving along, preconditions. How do you document a function that takes an array? Well, there's an obvious thing here
it must be that the size of the array has to be
a non-negative number, has to be positive actually. Okay, so we say parameter "size" is a positive integer, and "array[0] to array[size -1]",
must be valid data.
So, that pretty well lays it out. What has to be true for this to be a reasonable operating function. Okay, let's take a look at bubble sort again.
And at this point it's important to understand,
just what happens when you send or when you pass an array to a function.
It acts very much like pass by reference. Actually what you are sending is the address of the first byte, of the first cell of the array. So,
when I pass "my_array" to this bubble sort, it will indeed sort the array in the calling function.
"my_array" will indeed be different when we return from this function.
So it is vitally important that when you've got a
function that you send an array to, for instance this last one, here where it is "print_array",
if it's not to change that array, and it is an array parameter,
it is really important to make that a "const'
to say, "compiler, don't let this change."
Okay, back to our bubble sort
we do not want to be a constant, we want it to be an array of floats,
it we put "const" on there, then it wouldn't change the array, it woudn't actually sort it.
Now, the second point I want to make here is, notice this line of code. I replaced the embedded code in our old bubble sort, the swap
mechanism, those three lines of code with a function call here. We, I think I showed you in a earlier a lesson, templated code how I could
swap two variables, two values, with a function call.
So that makes the code a little bit shorter, little bit neater. This one other thing I'd like to do here, I want to show how you would template this code.
Instead of just being able to bubble sort
an array of floats, I'm gonna do it with an array of anything. Here we go, see if I can write this neat enough. I have to tell the compiler
and "T" is my template parameter and that means that
it not a float but "T". And the only other thing that I need to be careful about is the swap. The swap would have to be templated also.
So, you would have to write a templated swap function, which would look something like this: "template ", "void swap"
T referece t1, T reference t2 and the definition.
So now I can apply this swapping routine to an array of anything.
Here is another function, "shift_right", I pass an array of ints to it, and what it's going to do is shift everything to the right.
So, before it looks like 12,14,15,18,31,
and afterwards it'll be 12,14,15,18 and sure enough, 12,14,15 and 18. And, again if I want to template this,
then I can write 'template", and I'll use "typename" here. Or, could be "class",
"" and this would no longer be an array of ints, but an aray of "T",
and I don't believe anything else has to change.
Here we have a function called "is_found". I'm going to supply this function with an array of characters,
I'm not going to change that array, so slap a const, I send it the size, and I send it a character
that I call "target". It's not going to change, so I slap a const on that,
and create a local variable called "found", initialize it to false, a counter variable "i" initialize it to zero.
Jump into a while loop, while "i" is less than the size and "found" is false,
I'm going to ask the question, if "target" is equal to the "array[i]", then "found" is true. And then increase, increment "i".
And it will run down this array, not with a for loop but with a sentinel loop looking to see if target is in the array and it'll return true if it is,
false otherwise. Let's look at a different version of this. Here I'm going to send back not a bool, but an int.That's gonna be the "position_found"
and it's going to default to -1. So, what's the postcondition?
So, again it simply walks down that array and looks for the target in the array. And if it finds it, it will return that position, and otherwise
it's simply going to return -1. So, if you think about how you write your functions, you can actually return more information than you might otherwise
believe. The first version we sent back true or false. Was it there or was it not.
But, in the second version we can not only communicate that it wasn't there, but also if it's there, where it is. Where its first instance is.
So, you see there is many, many things that you can do with arrays, and you are going to find them very, very useful
in your programming.