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:

Set the initial largest value to the value of the first element of the array.
Set the index value of the first element, value 0.
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.
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:

Set the accumulator variable, sum, to the value of the first element of the array.
For each of the other elements of the array, add the value of the next element in the array to the accumulator variable.
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:

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.
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 log₂N.

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:

Set the lower and upper bounds of the array to search.
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.
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
Insertion sort
Merge sort
Bubble sort
Shell sort

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:

For all elements with index J = 0 to N-2, carry out steps 2 and 3.
Search for the smallest element from index J to N-1.
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 N²/2 - N/2. The first term (N²/2) in this expression is the dominant one; the order of growth of this algorithm is N². This is formally expressed as O(N²).