Fundamental Programming
Array Processing
Bimo Sunarfri Hantono
Electrical Engineering and Information Technology
Universitas Gadjah Mada
Array Processing
Objective
To introduce arrays and the uses off arrays
To develop pseudocode algorithms for common operations on
arrays
To illustrate the manipulation of single- and two-dimensional arrays
Outline
Array processing
Initializing the elements of an array
Searching an array
Writing out the contents of an array
Programming examples using arrays
Two-dimensional arrays
Array Processing
One of the most powerful programming tools available
Help to organize a collection of homogeneous data items
(same type and length). The individual data items that make
up the array are called as element of the array
Example:
element(index)
Scores(3) indicated the third exam score
Arrays are an internal data structure that is, they are required
only for the duration of the program in which they are defined
Operations on Arrays
Arrays can be used:
to load initial information into an array that is later required for
processing
to process the elements of the array
to store the results of processing into the elements of an array, or
to store information, which is then written to a report.
The most typical operations performed on arrays are:
loading a set of initial values into the elements of an array
processing the elements of an array
searching an array, using a linear or binary search, for a particular
element
writing out the contents of an array to a report.
Simple Algorithm That Manipulate
Arrays
Each algorithm is written using a DO loop
The contents of the array and the number of elements have
been established and the subscript is named 'index
The number of elements in the array is stored in the variable
number_of_elements.
Find the sum of the elements of an array
Each element of the array is accumulated into a variable
called sum. When all elements have been added, the variable
sum is printed.
Find_sum_of_elements
Set sum to zero
DO index = 1 to number_of_elements
sum = sum + array(index)
ENDO
Print sum
END
Find the average of the elements of an array
Each element of the array is accumulated into a variable
called sum. When all elements have been added, the average
of the elements is found and printed.
Find_element_average
Set sum to zero
DO index = 1 to number_of_elements
sum = sum + array(index)
ENDO
Average = sum / number_of_elements
Print Average
END
Find the largest elements of an array
The elements of an array are searched to determine which
element is the largest. The algorithm starts by putting the first
element of the array into the variable largest_element, and
then looks at the other elements of the array to see if a larger
value exists. The largest value is then printed.
Find_largest_element
Set largest_element to array(1)
DO index = 2 to number_of_elements
IF array(index) > largest_element THEN
largest_element = array(index)
ENDIF
ENDO
Print largest_element
END
Find the smallest of the elements of an array
The elements of an array are searched to determine the
smallest element. The algorithm starts by putting the first
element of the array into the variable smallest_element, and
then looks at the other elements of the array to see if a smaller
value exists. The smallest value is then printed.
Find_smallest_element
Set smallest_element to array (1)
DO index = 2 to number_of_elements
IF array(index) < smallest_element THEN
smallest_element = array(index)
ENDIF
ENDO
Print smallest_element
END
Find the range of the elements of an array
The elements of an array are searched to determine the
smallest and the largest elements. The algorithm starts by
putting the first element of the array into the variables
smallest_element and largest_element, and then looks at the
other elements to see if a smaller or larger value exists. The
two values are then printed.
Find the range of the elements of an array
Find_range_of_element
Set smallest_element to array(1)
Set largest_element to array(1)
DO index = 2 to number_of_elements
IF array(index) < smallest_element THEN
smallest_element = array(index)
ELSE
IF array(index) > largest_element THEN
largest_element = array(index)
ENDIF
ENDIF
ENDO
Print the range as smallest_element followed by
largest_element
END
Initializing the elements of an array
Because an array is an internal data structure, initial values
must be placed into the array before any information can be
retrieved from it.
The initial values can be assigned to the element as constant
or be read from file.
Loading constant values into array
Loading constant values into an array (only be used for data
which is unlikely to be changed)
Loading initial values into an array from an input file
Initialize_month_table
month_table(1) = `January`
month_table(2) = `February`
.
.
.
month_table(12) = `December`
END
Loading initial values into an array
from an input file
A common procedure is to read the input values into the
elements of an array from an input file
DOWHILE loop : The loop should terminate when either the
array is full or the input file has reached end of file
Loading initial values into an array
from an input file
Read_values_into_array
Set max_num_elements to required value
Set index to zero
Read first input value
DOWHILE (input value exist) AND (index < max_num_elements)
index = index + 1
array(index) = input value
Read next input value
ENDDO
IF (input value exist) AND index = max_num_elements
THEN
Print `Array size is too small`
ENDIF
END
Arrays of variable size
the number of entries in an array can vary
a sentinel value is used to mark the last element of the array,
both in the initializing file of data items and in the array itself
Arrays of variable size
Read_values_into_variable_array
Set max_num_elements to required value
Set index to zero
Read first input value
DOWHILE (input value NOT = 9999) AND (index < max_num_elements)
index = index + 1
array(index) = input value
Read next input value
ENDDO
IF index < max_num_elements THEN
index = index + 1
array(index) = 9999
ELSE
Print `Array size is too small`
ENDIF
END
Paired Arrays
Two array with the same number of elements are paired
because they correspond each other.
Example:
A student number ID array and student name array
Paired Arrays
Read_values_into_paired_array
Set max_num_elements to required value
Set index to zero
Read first input value
DOWHILE (NOT EOF input record) AND (index < max_num_elements)
index = index + 1
product_codes(index) = input_product_code
selling_prices (index) = input_selling_price
Read next record
ENDDO
IF (NOT EOF input record) AND index = max_num_elements THEN
Print `Array size is too small`
ENDIF
END
Searching an Array
The reasons for searching an array may be:
to edit an input value that is, to check that it is a valid element of
an array
to retrieve information from an array
to retrieve information from a corresponding element in a paired
array.
A linear search of an array
Linear_search_of_an_array
Set max_num_elements to required value
Set element_found to false
Set index to 1
DOWHILE (NOT element_found) AND (index <= max_num_elements)
IF array(index) = input_value THEN
Set element_found to true
ELSE
index = index + 1
ENDIF
ENDDO
IF element_found THEN
Print array (index)
ELSE
Print value not found , input_value
ENDIF
END
A binary search of an array
Binary_search_of_an_array
Set element_found to false
Set low_element to 1
Set high_element to max_num_elements
DOWHILE (NOT element_found) AND (low_element <= high_elements)
index = (low_element + high_element)/2
IF input_value = array(index) THEN
Set element_found to true
ELSE
IF input_value < array (index) THEN
high_element = index 1
ELSE
low_element = index + 1
ENDIF
ENDIF
ENDDO
IF element_found THEN
Print array (index)
ELSE
Print value not found , input_value
ENDIF
END
Writing out the contents of an array
The elements of an array can be used as accumulators of
data, to be written to a report.
Writing out the contents of an array involves starting with the
first element of the array and continuing until all elements have
been written.
Write_values_of_array
DO index = 1 to number_of_elements
Print array (index)
ENDDO
END
Programming Example Using Array
Process exam scores
Design a program that will prompt for and receive 18
examination scores from a mathematics test, compute the
class average, and display all the scores and the class
average to the screen.
Process exam scores
Defining diagram
Input
18 exam scores
Processing
Prompt for scores
Get scores
Compute class average
Display scores
Display class average
Output
18 exam scores
class_average
Process exam scores
Control Structures required
An array to store the exam scores called scores
An index to identify each element in the array
A DO loop to accept the scores
Another DO loop to display the scores to the screen.
Process exam scores
Solution algorithm
Process_exam_scores
Set total_score to zero
DO index = 1 to 18
Prompt operator for score
Get scores(index)
total_score = total_score + scores(index)
ENDDO
Compute average_score = total_score / 18
DO index = 1 to 18
Display scores(index)
ENDDO
Display average_score
END
Process integer array
Design an algorithm that will read an array of 100 integer
values, calculate the average integer value, and count the
number of integers in the array that are greater than the
average integer value. The algorithm is to display the average
integer value and the count of integers greater than average.
Process integer array
Defining diagram
Input
100 integer values
Processing
Read integer values
Compute integer average
Compute integer count
Display integer average
Display integer count
Output
integer_average
integer_count
Process integer array
Control Structures required
An array of integer values called numbers
A DO loop to calculate the average of the integers
Another DO loop to count the number of integers greater than the
average.
Process integer array
read?
Solution algorithm
Process_integer_array
Set integer_total to zero
Set integer_count to zero
DO index = 1 to 100
integer_total = integer_total + numbers(index)
ENDDO
integer_average = integer_total / 100
DO index = 1 to 100
IF numbers(index) > integer_average THEN
add 1 to integer_count
ENDIF
ENDDO
Display integer_average, integer_count
END
Validate sales number
Design an algorithm that will read a file of sales transactions
and validate the sales numbers on each record. As each sales
record is read, the sales number on the record is to be verified
against an array of 35 sales numbers. Any sales number not
found in the array is to be flagged as an error.
Validate sales number
Defining diagram
Input
sales records
sales_number
Processing
Read sales records
Validate sales numbers
Print error message
Output
error_message
Validate sales number
Control Structures required
A previously initialized array of sales numbers, called
sales_numbers
A DOWHILE loop to read the sales file
A DOWHILE loop to perform linear search
A variable element_found to stop the search
Validate sales number
Solution algorithm
Validate_sales_numbers
Set max_num_elements to 35
Read sales record
DOWHILE sales_records exist
Set element_found to false
Set index to 1
DOWHILE (NOT element_found) AND (index <= max_num_elements)
IF sales_numbers(index) = input sales number THEN
Set element_found to true
ELSE
index = index + 1
ENDIF
ENDDO
IF NOT element_found THEN
Print `invalid sales numer`, input sales number
ENDIF
Read sales record
ENDDO
END
Calculate shipping charge
Design an algorithm that will read an input weight for an item
to be shipped, search an array of shipping weights and
retrieve a corresponding shipping charge. In this algorithm,
two paired arrays, each containing six elements, have been
established and initialized. The array, shipping_weights,
contains a range of shipping weights in grams, and the array,
shipping_charges, contains a corresponding array of shipping
charges in dollars, as follows:
Calculate shipping charge
Shipping weights (grams)
Shipping charges
1 100
3.00
101 500
5.00
501 1000
7.50
1001 3000
12.00
3001 5000
16.00
5001 - 9999
35.00
Calculate shipping charge
Defining diagram
Input
entry weight
Processing
Prompt for entry weight
Get entry weight
Search shipping weights array
Compute freight charges
Display freight charge
Output
freight_charge
error_message
Calculate shipping charge
Control Structures required
Two arrays, called shipping_weights and shipping_charges`
A DOWHILE loop to search the shipping_weights array and then
retrieve the shipping_charges
A variable element_found to stop the search when entry weight is
found
Calculate shipping charge
Solution algorithm
Calculate_shipping_charge
Set max_num_elements to 6
Read index to 1
Set element found to false
Prompt for entry weight
Get entry weight
DOWHILE (NOT element_found) AND (index <= max_num_elements)
IF shipping_weights(index) < entry weight THEN
add 1 to index
ELSE
set element_found to true
ENDIF
ENDDO
IF element_found THEN
shipping_charge = shipping charges(index)
Display `shipping charge is`, shipping_charge
ELSE
Display `invalid shipping weight`, entry weight
ENDIF
END
Two-dimensional Arrays
Where two subscripts are required to locate an element in an
array.
The number of elements is calculated as the product of the
number of rows and the number of columns
Specified by: array(row_index, column_index)
One dimensional Array
Shipping weights (grams)
1 100
101 500
501 1000
1001 3000
3001 5000
5001 - 9999
Two dimensional Array
Shipping charges ($) (by shipping zone)
1
2.50
3.50
4.00
5.00
3.50
4.00
5.00
6.50
4.50
6.50
7.50
10.00
10.00
11.00
12.00
13.50
13.50
16.00
20.00
27.50
Loading a two-dimensional array
Read_values_into_array
Set max_num_elements to 24
Set row_index to zero
Read input file
DOWHILE (input values exist) AND (row_index < 6)
row_index = row_index + 1
DO column_index = 1 to 4
shipping_charges(row_index,column_index) = input value
read input file
ENDDO
ENDDO
IF (input values exist) AND row_index = 6 THEN
Print Array size to small`
ENDIF
END
Searching Two dimensional Array
Calculate_Freight_Charges
Set row index to 1
Set element_found to false
Prompt for shipping_weight, zone
Get shipping_weight, zone
DOWHILE (NOT element_found) AND (row_index <= 6)
IF shipping_weights (row_index) < input shipping_weight THEN
add 1 to row_index
ELSE
Set element_found to true
ENDIF
ENDDO
IF element_found THEN
IF zone = (1 or 2 or 3 or 4) THEN
freight_charge = freight_charge (row_index, zone)
Display 'Freight charge is', freight_charge
ELSE
Display 'invalid zone', zone
ENDIF
ELSE
Display 'invalid shipping weight', input shipping_weight
ENDIF
END
Search_employee_numbers
Set row_index to 1
Set employee_found to false
Read input employee_number
DOWHILE (NOT employee_found) AND (row_index <=10)
Set column_index to 1
DOWHILE (NOT employee_found) AND (column_index <= 5)
IF employee_numbers (row_index, column_index) = input
employee_number THEN
Set employee_found to true
ENDIF
column_index = column_index + 1
ENDDO
row_index = row_index + 1
ENDDO
IF NOT employee_found THEN
Print 'invalid employee number', input employee_number
ENDIF
END
Writing out the contents of 2-d array
Write_values_of_array
Set number_of_rows to required value
Set number_of_columns to required value
DO row_index = 1 to number_of_rows
DO column_index = 1 to number_of_columns
Print array (row_index, column_index)
ENDDO
ENDDO
END
Summary
Array as a data structure made up of a number of variables or
data items that all have the same data type and are accessed
by the same name.
Most Common operations on arrays:
loading a set of initial values into the elements of an array
processing the elements of an array
searching an array, using a linear or binary search, for a particular
element
writing out the contents of an array to a report
Arrays can be use for both one and two-dimension.
Thank You
