Object-Oriented Programming (From Problem Solving to JAVA) (Charles River Media Programming)

9.4 Simple Applications of Arrays

This section includes several simple and typical applications of arrays. Class Temp is used as an implementation for these discussions. The first part of class Temp includes the various data definitions including array temp.

class Temp is protected constants integer NUM_TEMP = 15 // array capacity variables integer t_index integer num_temp_values // number of elements float temp array [NUM_TEMP] ...

9.4.1 Finding Maximum and Minimum Values in an Array

To find the minimum and/or maximum values stored in an array, all the elements have to be examined. The algorithm for finding the maximum value in informal pseudo-code (as a sequence of steps) is:

  1. Set the initial largest value to the value of the first element of the array.

  2. Set the index value of the first element, value 0.

  3. Carry out the following steps for each of the other elements of the array:

    1. Examine the value of the next element in the array.

    2. If the value of the current element is greater than the largest value so far, update the value found so far with this element value, and save the index of the element.

  4. The result is the index value of the element value found to be the largest in the array.

The algorithm uses two intermediate (or temporary) variables that are used to store the largest value found so far, max_val, and the index value of the corresponding element, jmax.

Function maxtemp in class Temp implements the algorithm discussed. The function uses array temp, which is declared in the class as an array of type float and that has num_temp_values elements. The function returns the index value with the largest value found.

description This function returns the index of the element with the maximum value in the array. */ function maxtemp of type integer is variables integer j // index variable // index of element with largest value integer jmax float max_val // largest value so far begin set jmax = 0 // index first element set max_val = temp[0] // max value so far for j = 1 to num_temp_values - 1 do if temp[j] > max_val then set jmax = j set max_val = temp[j] endif endfor return jmax // result endfun maxtemp

The minimum value can be found in a similar manner; the only change is the comparison in the if statement.

9.4.2 Calculating the Average Value in an Array

To find the average value in an array, all the elements have to be added to an accumulator variable, sum. The algorithm for computing the average value in informal pseudo-code (as a sequence of steps) is:

  1. Set the accumulator variable, sum, to the value of the first element of the array.

  2. For each of the other elements of the array, add the value of the next element in the array to the accumulator variable.

  3. Divide the value of the accumulator variable by the number of elements in the array. This is the result value calculated.

The algorithm uses an accumulator variable that is used to store the summation of the element values in the array. In an array x with n elements, the summation of x with index j starting with j = 1 to j = n is expressed mathematically as:

The average is calculated simply as sum/n. Function average_temp in class Temp implements the algorithm discussed. The function uses array temp, which is declared in class Temp as an array of type float and that has num_temp_values elements. The function returns the average value calculated. The KJP code for the function follows.

description This function computes the average value of the array temp. The accumulator variable sum stores the summation of the element values. */ function average_temp of type float is variables float sum // variable for summation float ave // average value integer j begin set sum = 0 for j = 0 to num_temp_values - 1 do add temp[j] to sum endfor set ave = sum / num_temp_values return ave endfun average_temp

9.4.3 Searching

When the elements of an array have been assigned values, one of the problems is to search the array for an element with a particular value. This is known as searching. Not all the elements of the array need to be examined; the search ends when and if an element of the array has a value equal to the requested value. Two important techniques for searching are linear search and binary search.

9.4.3.1 Linear Search

Linear search is also known as sequential search, because the method starts to compare the requested value with the value in the first element of the array, and if not found, compares with the next element, and so on until the last element of the array is compared with the requested value.

A useful outcome of this search is the index of the element in the array that is equal to the requested value. If the requested value is not found, the result is a negative value. The algorithm description in informal pseudo-code (as a sequence of steps) is:

  1. For every element of the array and until the value is found:

    1. Compare the current element with the requested value. If the values are equal, store the value of the index as the result and search no more.

    2. If the values are not equal, continue the search.

  2. If the value requested is not found, set the result to a negative value.

Function searchtemp in class Temp searches the array for an element with the requested temperature value. For the result, the function assigns to t_index the index value of the element with the value requested. If the requested value is not found, the function assigns a negative integer value to t_index. The code for the KJP implementation of function searchtemp follows.

description This function carries out a linear search of the array of temperature for the temperature value in parameter temp_val. It sets the index value of the element found, or -1 if not found. */ function searchtemp parameters float temp_val is variables integer j boolean found = false begin set j = 0 while j < num_temp_values and found not equal true do if temp [j] == temp_val then set t_index = j set found = true else increment j endif endwhile if found not equal true then set t_index = -1 endif endfun searchtemp

9.4.3.2 Binary Search

Binary search is a more efficient search technique than linear search, because the number of comparisons is smaller. The efficiency of a search algorithm is determined by the number of relevant operations in proportion to the size of the array to search. The relevant operations in this case are the comparisons of the element values with the requested value.

For an array with N elements, the average number of comparisons with linear search is N/2, and if the requested value is not found, the number of comparisons is N. With binary search, the number of comparisons is log2N.

The binary search technique can only be applied to a sorted array. The values to be searched have to be sorted in ascending order. The part of the array elements to include in the search is split into two partitions of about the same size. The middle element is compared with the requested value. If the value is not found, the search is continues on only one partition. This partition is again split into two smaller partitions until the element is found or until no more splits are possible (not found).

Class Temp declares an array of temperatures named temp. One of the functions reads the element values from the console, another function reads the value of temperature to search, and a third function searches the array for the requested temperature value and returns the index value or a negative integer value.

The description of the algorithm, as a sequence of steps, is:

  1. Set the lower and upper bounds of the array to search.

  2. Continue the search while the lower index value is less than the upper index value.

    1. Split the section of the array into two partitions. Compare the middle element with the requested value.

    2. If the value of the middle element is the requested value, the result is the index of this element-search no more.

    3. If the requested value is less than the middle element, change the upper bound to the index of the middle element minus 1. The search will continue on the lower partition.

    4. If the requested value is greater or equal to the middle element, change the lower bound to the index of the middle element plus 1. The search will continue on the upper partition.

  3. If the value is not found, the result is a negative value.

Function bsearchtemp in class Temp implements the binary search algorithm using array temp. The code for the KJP implementation for this function follows.

description This function carries out a binary search of the array of temperature for the temperature value in parameter temp_val. It sets the index value of the element found, or -1 if not found. */ function bsearchtemp parameters float temp_val is variables boolean found = false integer lower // index lower bound element integer upper // index upper bound element integer middle // index of middle element begin set lower = 0 set upper = num_temp_values while lower < upper and found not equal true do set middle = (lower + upper) / 2 if temp_val == temp[middle] then set found = true set t_index = middle else if temp_val < temp [middle] then set upper = middle -1 else set lower = middle + 1 endif endif endwhile if found not equal true then set t_index = -1 endif endfun searchtemp

On the CD

The complete implementation of class Temp is stored in the file Temp.kpl. The Java implementation of this class is stored in the file Temp.java.

9.4.4 Sorting

Sorting an array consists of rearranging the elements of the array in some order according to the requirements of the problem. For numerical values, the two possible sorting orders are ascending and descending. There are several sorting algorithms; however, some are more efficient than others. Some of the most widely known sorting algorithms are:

Selection sort is the only one explained here; it is a very simple and inefficient sorting algorithm. Assume there is an array of a numerical type of size N; the algorithm performs several steps. First, it finds the index value of the smallest element value in the array. Second, it swaps this element with the element with index 0 (the first element). This step actually places the smallest element to the first position. Third, the first step is repeated for the part of the array with index 1 to N - 1; this excludes the element with index 0, which is at the proper position. The smallest element found is swapped with the element at position with index 1. This is repeated until all the elements are located in ascending order. A more precise description of the algorithm, as a sequence of steps, is:

  1. For all elements with index J = 0 to N-2, carry out steps 2 and 3.

  2. Search for the smallest element from index J to N-1.

  3. Swap the smallest element found with element with index J, if the smallest element is not the one with index J.

Class Temp declares an array temp of type float. The array declaration is:

float temp array [NUM_TEMP]

Function selectionsort in class Temp implements the algorithm for the selection sort. The code for the KJP implementation for this function follows.

description This function carries out a selection sort of the array of temperature. */ function selectionsort is variables integer N // elements in array integer Jmin // smallest element integer j integer k float t_temp // intermediate temp begin set N = num_temp_values for j = 0 to N - 2 do // search for the smallest element // in the index range from j to N-1 set Jmin = j for k = j+1 to N - 1 do if temp[k] < temp [Jmin] then set Jmin = k endif endfor if Jmin != j then // swap elements with index J and Jmin set t_temp = temp[j] set temp[j] = temp [Jmin] set temp[Jmin] = t_temp endif endfor endfun selectionsort

The selection sort is not a very efficient algorithm. The number of element comparisons with an array size of N is N2/2 - N/2. The first term (N2/2) in this expression is the dominant one; the order of growth of this algorithm is N2. This is formally expressed as O(N2).

Related

Категории