CHAPTER 5 – ARRAYS

CASE STUDY SCENARIO

Sorting Data

A dozen umbrellas lie on the ground just inside the classroom door when Dr. Taylor begins his lecture. “A cold, rainy day like today makes me want to stay in and order pizza for delivery rather than go out myself.” Handing a phone book to a student in the front row, Dr. Taylor says “Gail, please look up the phone number for Domino’s Pizza on Main Street, and if you don’t mind, I will time how long it takes you to find the number.” Gail flips through a few pages while Dr. Taylor looks at his watch. “Here it is . . . 555-8275,” she says.

“Seven seconds. Thank you Gail.” Dr. Taylor presses some keys on his cell phone while continuing his conversation. “Now please look up the name of the person with the phone number 555-5982, and again I will time you.” Dr. Taylor’s focus returns to his watch even as he speaks into the phone. Gail slowly flips a couple of pages, then stops just about the same time Dr. Taylor ends his call. “I assure you the number is in there, Gail. We will wait while you look it up.”

“You will probably wait a long time,” she says, “because there is no fast way to find a number.”

“Why not? It’s the same data.”

“But the phone book is sorted by names, so finding a name is easy. Finding a number is very difficult because a phone book is not sorted by numbers.”

Dr. Taylor takes the phone book from Gail. “Exactly! The sorting process does not change the data, but it organizes the data in a context, making it useful information. Sorting is a fundamental processing activity, and we will discuss it very soon.

“But first, we need to discuss arrays, which are a useful means to hold large amounts of data, sorted or unsorted.”

Dr. Taylor’s sorting solution is presented later in this chapter.

Arrays

Sometimes it is beneficial to work with related data items as a single group. For example, all the scores from an entire class of students, all the names of employees for a company, or all the batting averages of the players on a baseball team. The easiest and most common way to store such related data is with an array.

An array is a variable that holds a collection of related data values. Each of the values in an array is called an element. Each element is like a separate variable, capable of storing and recalling a value as needed. Elements are uniquely identified by an integer value called its index, which indicates the position of the element in the array. The lowest index value is zero, and the largest index value is called the upper bound. Each element of an array is like a separate variable, capable of storing and recalling a value. To reference an element you must specify both the array name and the specific index value.

Creating an Array

In Visual Logic you create, or declare, an array using the Make Array command. The Make Array edit dialog contains a text box for entering the name of the array and its upper bound. Figure 5-1 shows the Visual Logic Make Array dialog box for creating an array named “Scores” with an upper bound of 8. The resulting array is shown in Figure 5-2.

[pic]

FIGURE 5-1: An Example of the Make Array Edit Dialog Box

[pic]

FIGURE 5-2: The Scores Array created by the Make Array command in Figure 5-1

Accessing Individual Elements of an Array

To access individual array elements, you specify the array name and follow it with an index expression enclosed in parentheses. The value of the expression determines which element to access. The index to an array can be a constant, a variable, or an expression. For example, Scores(5) references the element with index value 5 in the array named Scores. Likewise, if K has the value 5, then Scores(K) also references the same element. Finally, if A is 2 and B is 3, then Scores(A + B) would also reference the index 5 element. Figure 5-3 includes a flowchart that creates an array and then assigns four values to that array. The resulting state of the array after the flowchart code is complete is also shown in Figure 5-3.

[pic]

FIGURE 5-3: A flowchart with four array assignments and the resulting array elements

TIP

Each element of an array is like a separate variable, capable of storing and recalling a value.

TIP

Whenever you reference an element you must specify the array name followed by the index value inside parentheses.

TIP

Arrays contain a finite number of elements, each of which is referenced by a unique index. If you attempt to reference an array with an index value greater than the upper bound of the array, the result will be an out-of-bounds error. For example, a reference to Scores(9) in the Figure 5-3 array would generate an out-of-bounds error because the index value 9 is greater than the upper bound for this array.

Array Summary

• An array is a storage location that holds a collection of related data.

• The values in the array are called the array elements.

• Individual elements in an array are identified by means of an index. Index values are integer values from 0 to the upper bound of the array.

• When referencing an element of an array, start with the array name and then specify the desired index inside parentheses.

• The index value that references an array can be provided by an integer constant, an integer variable, or an integer expression. This gives a great deal of power to developers when using arrays.

Benefits of Using an Array

Arrays are valuable tools for developers. But what exactly is it about arrays that make them so helpful? One answer is that arrays combine the power of loops with the power of multiple storage locations. Consider briefly the following two problems:

(Problem #1) Input 5 numbers and output their average.

(Problem #2) Input 5 numbers and display the numbers in reverse order.

These two problems can both be solved without using arrays, but the two solutions will be very different. Figure 5-4 shows a common solution to both. The first problem would most likely be solved using a loop to minimize the inputs and allow the program to easily be modified to handle 50 or 500 inputs. The second problem requires 5 different storage locations and therefore a loop cannot be used. Furthermore the second solution would be time consuming and monotonous to modify to handle 12 or 500 inputs.

[pic]

FIGURE 5-4: A Loop Solution to Calculate Average and a Multi-Variable Solution to Reverse Order

The point of Figure 5-4 is to show that there are times when loops are desirable and there are times when separate storage locations are desirable. Now image a third problem that combines both of the previous problems. To make the problem even more interesting, assume there are 12 input values (rather than just 5).

(Problem #3) Input 12 numbers and output their average and then display the input numbers in reverse order.

Neither solution in Figure 5-4 is could be easily modified to solve this problem. (Take a few minutes if necessary to convince yourself that the previous statement is true.) However this problem is easily solved using an array, as shown in Figure 5-5. The array solution combines the best features of the two programs from Figure 5-4, including having only a single input statement inside a loop, while also storing all the input values so nothing is lost.

When referencing an array inside the body of a loop, the loop variable is often used as the array’s index value. As the loop variable changes from 1 to 2 to 3 to 4 (and so on) so also the array index changes from 1 to 2 to 3 to 4 (and so on). This allows the loop to process each element of the array.

TIP

In this book, we will not use the array element at index 0, and instead will store the first array value at index 1, the second array value at index 2, the third array value at index 3, and so on. This will make the programs easier to read and understand.

[pic]

FIGURE 5-5: An Array Solution that Calculates Average and Displays Values in Reverse Order

[pic]

FIGURE 5-6: Sample Output from Figure 5-5

TIP

Many programs that utilize arrays will also employ For loops, with the For loop variable used as the index value for the array. Notice in Figure 5-5 that the first loop has the loop variable myCount and the first loop body uses myCount as the index value for the array in both the input and assignment statement. Then notice that the second loop has the loop variable K and the second loop body uses K as the index value for the array in the output statement. The general principle illustrated here is that when using a For loop to process an array, inside the body of that loop the For Loop variable is often used as the array index value.

Benefits of Using an Array Summary

• An array can be used to store multiple values in a single storage location. This makes the code easy to read and easy to work with.

• Arrays get their full power when used in conjunction with loops, where the body of the loop containing a reference to the array, and the loop variable is used as the index value for the array.

Sample Program #1: Evens and Odds

Write a program that declares and array named List with an upper bound of 10. The program should prompt the user for ten values and store them into the array. The program should then calculate and display the average of the ten values. The program should then display the even values and their average, and the program should display the odd values and their average.

Analysis and Design

Let’s break this problem apart into separate requirements:

1. Write a program that declares and array named List with an upper bound of 10.

2. The program should prompt the user for ten values and store them into the array.

3. The program should then calculate and display the average of the ten values.

4. The program should then display the even values and their average.

5. The program should then display the odd values and their average.

Now that the problem has been broking into separate steps, these smaller pieces can be solved individually. Solving all the smaller pieces will therefore solve the larger problem. This technique is sometimes called “Divide and Conquer” and it works well for this problem. Figure 5-7 shows the solution to this problem, with the code for the individual requirements indicated.

The first requirement is satisfied by an appropriate Make Array command, being sure to use the required array name and upper bound value.

The second requirement is satisfied by an Input statement inside of a For loop. Note that the For loop variable, J, is used as the array index value List(J) in the Input statement.

The third requirement involves calculating an average, which means the program needs a total and a count. The count is known (it will be the average for all 10 values) and the total can be calculated inside a loop. One the total has been generated, the average can be determined with a simple calculation.

The fourth requirement is to display the even values and their average. This requires a conditional test on each value in the array to see if the value is even (e.g., divisible by 2 with no remainder). If the value is even it should be displayed, counted and added to the appropriate total. After all even values have been found, the appropriate total and count values can be used to calculate and display the even average.

The fifth requirement is similar to the fourth and also requires testing each element in the array to see if the value is odd, and updating appropriate count and total values if so. After all odd values have been found and displayed, the appropriate count and total values are used to calculate and display the odd average.

By breaking the problem up into separate requirements and solving the individual pieces, we can solve the entire problem. Note that Figure 5-7 contains four loops and that the loop variable is different each time (J, K, M, N). Because these are not nested loops, we could have reused the same variable name each time. However separate loop variables are used intentionally in Figure 5-7 to point out that the array index variable depends on the loop in which the statement appears. In other words, inside the K loop the array index is List(K), and inside the M look the array index is List(M). Figure 5-8 shows the output generated by this program.

TIP

The idea of breaking a problem down into smaller part and solving those smaller parts individually is one of the main reasons for the use of procedures, which is discussed in Chapter 6.

[pic]

FIGURE 5-7: Solution to Sample Program #1: Even and Odds

[pic]

FIGURE 5-8: Sample Output from Figure 5-7

Sample Program #2: Dice Roll Simulation

Computer simulations are powerful tools for studying the behavior of certain types of systems. In fact, today’s engineer would never consider launching a satellite or producing a new automobile design without first creating computer simulations to model the product’s behavior and functionality. While satellite and automobile performance simulations are beyond our current ability, a simple simulation such as rolling a single dice is something we can explore. Consider the following:

A single die is equally likely to roll a 1, 2, 3, 4, 5, or 6.While no single roll can be predicted, if the die is rolled many times, the roll values should move toward an even distribution. Specifically, as the number of rolls increases, the distributions should become closer to one-sixth, or 16.67%. Write a program that simulates rolling a single die many times. The program should maintain a count of how many times each of the six values was rolled. After all the rolls have been made, the program should display the totals of how many times each value was rolled.

Write a program that performs a simulation of a single die rolled many times. The program should keep a running total of how many times each of the six values have been rolled. This running total should be kept in an array with an upper bound of 6. For example, every time the roll value is 3, the program should increment (or increase by one) the value in the array at index 3. After the simulation is done rolling and counting, the program should display the total number of times each die value was rolled. Additionally, the program could present the simulation results in a visual manner as a histogram.

Analysis and Design

This simulation requires a means to approximate the rolling of a die. This can be done using the expression Random(6) + 1. Random(6) produces a random integer between 0 and 5 and adding 1 to the result produces random values between 1 and 6, which is exactly what this simulation needs.

The problem also requires six different counter variables to keep up with how many times each of the six values were rolled. Using an array to hold the six counter values has the benefit that the random value can be used as the index of the array. In other words, Counters(5) holds a count of how many times 5 was rolled, and each time the random roll value is 5 then the Counters(5) value is updated to be increased by 1.

Finally, after all the values have been rolled and counted, the program displays the totals and their percentages as well as a histogram of the data. The histogram is generated using nested loops. The inner loop generates a horizontal line of circles whose length is determined by the counter value (one circle for each time the die value was rolled). Following the loop to print the circles is an output with a carriage return to terminate the line. The outer loop then repeats the inner loop process for each of the six roll values.

The complete solution is shown in Figure 5-9. Two sample outputs with four hundred rolls are presented in Figure 5-10. Each run will be slightly different because random values will generate different totals.

[pic]

FIGURE 5-9: Solution to Sample Program #2 Dice Roll Solution

[pic]

[pic]

FIGURE 5-10: Sample Outputs from running Figure 5-9 twice
(Notice how the random values produce different results)

Sample Program #3: Parallel Arrays (Username and Password)

In this section we examine a problem that involves maintaining two parallel arrays. The first array holds usernames and the second array holds passwords. The two arrays are separate but related, each having the same number of elements and the values in one correspond to the values in the other. For example, the seventh element in the username array and the seventh element in the password array together form a valid username/password combination that would grant authentication to the system.

Write a program that reads 10 usernames and passwords pairs and stores those username and password values into parallel arrays. After the arrays have been loaded, the program should behave as a login screen, prompting for a username and a password. Based on the data entered for username and password, the program should respond appropriately with one of three output messages. If the username does not match one of the values in the username array, then the message should be “Username not found.” If the user-name is found in the username array, but the password does not match the parallel value in the password array, then the message should be “Username and password do not match.” If the username is found and the password matches the parallel value in the password array, the message should be “Access granted.”

Reading Data from a Text File

In addition to Dialog and Console input, there is a third input option called File input which allows the input data to come from a text file rather than being manually typed in each time the program is executed. In this program, for example, the 10 username and password pairs can be entered one time into a simple text file and those values can then be read from the text file into the parallel arrays each time the program is executed. This will eliminate redundant typing and reduce the likelihood of a typing error.

To perform file I/O, double-click on the Input (or Output) element to show the edit dialog, click "More >>", select the File option button, and then specify the appropriate text file name.

TIP

The authors have created a usernames.txt input file for this program which may be made available to you, or your instructor may have created an input file for you to use. At the same time, you can create your own input file as well using Notepad or a similar tool to create a simple .txt file. When creating an input file, remember that each line in the file corresponds to one input value. You should therefore keep the input file to one input item per line, being sure to include quotes around string input, just like with console or dialog input.

Four tips to remember when doing file I/O:

1. First, when creating your input text file, DO use quotes around string data inside the text file. (Note that File input works the same as Console input in that strings must have delimiting quotes, and that the delimiters can be either single or double quotes, just so long as you use the same delimiter to start and stop the string.)

2. Second, do NOT use quotes around the text file name in the I/O dialog.

3. Third, if your file name in the I/O dialog box uses a relative reference (without the full path name), the file needs to be in the same folder as the Visual Logic .exe executable (which is not necessarily the same folder as the *.vls solution file).

4. Fourth, if you have both FileInput and FileOutput in the same program, you must use different filenames for the Input and Output files.

Ask The Author:

Q: Are usernames and passwords typically saved as text files?

A: No. (Thank goodness.) A text file with usernames and passwords would not be very secure and you certainly would not want your bank account information stored in this format. An enterprise system would most likely store username and password data in a password protected database.

Analysis and Design

We begin our implementation of the username and password solution by confirming that we have a valid text file with username and password pairs. Figure 5-11 shows the username password pairs from the username.txt file. Note that the first four username password pairs are “peanut butter”/”jelly”, “sunrise”/”sunset”, “light”/”dark”, and “forward”/”reverse”. Those values are read and stored into parallel arrays which will look like Figure 5-12.

[pic]

FIGURE 5-11: Usernames.txt Input File

[pic]

FIGURE 5-12: Parallel Arrays after Reading Data from Input File

Now that the parallel arrays have their data, the program prompts the user for a username. The program checks the users input against the Username array looking for a match. If the entire array is searched and no match is found then the program gives the “Username not found” error message. If the username is found, the program prompts the user to input the associated password. The program then looks in the Password array at the same index value location where the Username was found. If the user entered password matches the associated password in the parallel array, then the program gives the “Access granted” message, otherwise the program gives the “Username and password do not match” error message. The solution to this problem is shown in Figure 5-13, and three sample runs are shown in Figure 5-14.

[pic]

FIGURE 5-13: Solution to Sample Program #3 Parallel Arrays

[pic]
[pic]
[pic]
FIGURE 5-14: Output from Figure 5-13

CASE STUDY SOLUTION

Sorting Data

“Probably the simplest way to sort an array is a technique called Bubble Sort. The basic idea is to repeatedly compare two adjacent values and swap them if they are in the wrong order. The bigger values flow in one direction, and the smaller values flow in the other direction.” Dr. Taylor turns to the blackboard, draws an array with nine elements, and fills them with apparently random values.

“The heart of the solution is a loop from the start to the end of the array. The loop swaps adjacent elements if necessary as it goes. After one pass through the array, the largest value will have moved to the end of the array.” Dr. Taylor makes a few marks on the chalkboard to illustrate the eight comparisons needed to pass through the entire array and the resulting location of the largest element in the final position (see Figure 5-15).

“If you repeat the loop a second time, the second largest element will be placed in its proper location.” Dr. Taylor makes additional marks on the chalkboard to represent the second pass through the array (see Figure 5-16).

[pic]

FIGURE 5-15: Array after One Pass (one value guaranteed to be in proper location)

[pic]

FIGURE 5-16: Array after Two Passes (two values guaranteed to be in proper locations)

Dr. Taylor continues, “After two passes, there are two elements that are certain to be in their proper locations. Three passes ensure three elements are in the proper location and so on. Sorting the array therefore requires N-1 passes where N is the number of elements in the array. If N-1 elements are in the proper location, the Nth element must also be in the proper location.”

He then begins handing out a sheet with a solution similar to Figure 5-17 printed on it. “This handout shows a simple implementation of Bubble Sort. Notice the two loops we just discussed. The solution also includes code to display the sorted values.” Figure 5-18 shows the output generated by the solution in Figure 5-17.

“Are there other sorting algorithms?” Ed asks.

“Absolutely, and almost all of them run faster than Bubble Sort. But Bubble Sort is the easiest to understand, and it works fine with arrays of size five thousand or less. If the size of the array is significantly bigger than that, you will probably need to consider one of the faster, more complex sorting algorithms.”

A few more aspects of the Bubble Sort algorithm are discussed in the remaining few moments of the class. Finally, there is a knock on the classroom door by a Domino’s delivery person holding a flat, cardboard box. Dr. Taylor smiles, as the aroma of pepperoni and sausage pizza fills the room. Glancing at his watch, he announces, “My lunch has arrived with perfect timing. Class dismissed.”

[pic]

FIGURE 5-17: Case Study Solution - Bubble Sort

[pic]

FIGURE 5-18: Sample Output for Figure 5-17

CHAPTER SUMMARY

• An array is a variable that holds a collection of related data values. Each of the values in an array is called an element. Each element in the array is identified by an integer value called its index, which indicates the position of the element in the array.

• Most modern programming languages implement zero-based arrays, meaning that array index values begin with 0. The length of an array is the number of elements in the array. The upper bound of an array is the index of the last element.

• To access individual array elements, you specify the array name and follow it with an index expression enclosed in parentheses. The value of the expression determines which element to access.

• Arrays contain a finite number of elements, each of which is referenced by a unique index. If you attempt to reference an array with an index value greater than the upper bound of the array, the result will be an out-of-bounds error.

• Parallel arrays are two or more arrays whose elements are related by their positions in the arrays.

• Bubble Sort is a simple sorting technique involving multiple passes through the array, each pass comparing adjacent elements and swapping them if necessary.

KEY TERMS

✓ Array

✓ array length

✓ Bubble Sort

✓ element

✓ Index

✓ Make Array command

✓ out-of-bounds error

✓ parallel arrays

✓ upper bound

✓ zero-based arrays

REVIEW QUESTIONS

1. How is an array with five elements similar to having five different variables?

2. How is an array with five elements better than having five different variables?

3. What is the difference between an array index and an array element?

4. What is the difference between an array length and an array upper bound?

5. In Visual Logic, how is an array declared?

6. The index value for an array can be a variable. Explain how this is helpful when writing programs.

7. Identify some general recommendations for when an array should be used.

8. Consider the Bubble Sort solution in Figure 5-17. What is the purpose of the Temp variable? Explain why swapping two values could not be done without a third storage location.

PROGRAMMING EXERCISES

5-1. Reverse. Write a program that uses an array to accept ten input values and store them into an array. The program should then display those ten numbers in reverse order.

[pic]

5-2. Above Average. Write a program that accepts five input values and stores them into an array. The program should then display the average of the five numbers. Finally the program should display all the numbers in the array that are larger than the average of the five numbers.

[pic]

5-3. Target Value. Write a program that accepts ten input values and stores them into an array. After reading the ten values, the program should then input one more value which is called the target value. The program should then search through the array to calculate and display how many times the target value appears inside the array.

[pic]

5-4. Batting Average. Write a program that uses parallel arrays to determine the batting average for a baseball team by position. There are nine positions on a baseball team and your program should have parallel arrays with an upper bound of 9. Your program will read data in pairs; the first number will be between 1 and 9 and will represent the batter’s position, and the second number will be either 0 or 1 and will represent an out (0) or a hit (1). The program will continue to input data pairs until the sentinel value -1 is read. At that point the program should output the batting average for each of the nine positions. (Note: Batting average is the number of hits divided by the number of at bats. Therefore hits and at bats may be good values to store in parallel arrays.) The output shown below was generated using the input file “battingaverage.txt” which may be available from your instructor.

[pic]

5-5. Batting Average and Slugging Percentage. Write a program that uses parallel arrays to determine the batting average and slugging percentage for a baseball team by position. There are nine positions on a baseball team and your program should have parallel arrays with an upper bound of 9. Your program will read data in pairs; the first number will be between 1 and 9 and will represent the batter’s position, and the second number will be either a 0 (for a out) or a 1 (for a single) or a 2 (for a double) or a 3 (for a triple) or a 4 (for a home run). The program will continue to input data pairs until the sentinel value -1 is read. At that point the program should output the batting average and slugging percentage for each of the nine positions. (Note: Batting average is the number of hits divided by the number of at bats and slugging percentage is the total number of bases divided by the number of at bats. You might want to have three parallel arrays in your solution.) The output shown below was generated using the input file “battingandslugging.txt” which may be available from your instructor.

[pic]

5-6. Two Dice Simulation. Write a program that simulates the rolling of two dice many times. Each of the two dice should have a separate “Random(6) + 1” and the two random values should be added together to get the total of the two dice roll. After rolling the two dice, the total rolled should be updated in an array of counters. For example, if the random values were 3 and 4, then the dice total is 7, and the index 7 element should be incremented by one. Because the maximum roll possible for two dice is 12, your array of counters should have an upper bound of 12. Your program should simulate rolling the two dice many times (400 rolls is the number used in the figure below) and then display how many times each total was rolled, and the percentage for each total. Finally the program should display the roll totals visually by creating a histogram. Note: Each time you run your program you will get different totals and therefore a different histogram. In general the middle totals (such as 6, 7, 8) should be rolled more often than the extremes (2, 3, 4 on the low end, and 10, 11, 12 on the high end) because there are more combinations of two dice that result in those middle values.

[pic]

5-7. Access Granted. Write a program that reads 10 usernames and passwords pairs and stores those username and password values into parallel arrays. After the arrays have been loaded, the program should behave as a login screen, prompting for a username and a password. Based on the data entered for username and password, the program should respond appropriately with one of three output messages. If the username does not match one of the values in the username array, then the message should be “Username not found.” If the user-name is found in the username array, but the password does not match the parallel value in the password array, then the message should be “Username and password do not match.” If the username is found and the password matches the parallel value in the password array, the message should be “Access granted.” The program should use a loop and continue to prompt the user for a valid username and password pair until a valid pair is entered and access is granted.

[pic]

5-8. Olympic Judging. When judging an Olympic event, the highest and lowest judges’ scores are often dropped, and the remaining judges’ scores are averaged. Write a program that accepts six numeric values as input representing scores from six Olympic judges. The program should store those six values into an array. Your program should then use bubble sort to sort the scores in the array. Finally, your program should output the highest score, the lowest score, and the average of the other four scores.

[pic]