Next: Summary Up: Algorithms Previous: Desk-checking

Series Minimum and Maximum Algorithm

Consider the following requirement specification:

A user has a list of numbers and wishes to find the minimum value and the maximum value in the list. A program is required which will allow the user to enter the numbers from the keyboard and which will calculate the minimum and maximum values that are input. The user is quite happy to enter a count of the numbers in the list before entering the numbers.

A first version at an algorithm for this might be:

initialise.
get count of numbers.
enter numbers and find maximum and minimum.
output results.

The algorithm is now made completely general to allow for a list with no numbers in it, this may seem a bit stupid but it is not uncommon when writing a general-purpose function to allow for the possibility of null input. A user might change their mind after calling the program for example and it is sensible that the program should respond sensibly if the user enters zero for the count. Incorporating this into the algorithm above gives the next version:

initialise.
get count of numbers.
if count is zero
   then exit
   otherwise {
              enter numbers and find maximum
                                 and minimum.
              output results.
             }

Once the count of the numbers is known then a loop has to be executed that number of times, each time reading in a number and somehow using that number in finding the maximum and minimum of the numbers. In this loop the number of times the loop is executed is known, i.e. equal to the count of numbers. Thus another type of repetition command is introduced:

loop n times
  {
   body of loop.
  }

This operation of repeating some set of instructions, the body of the loop, a set number of times occurs frequently in algorithm design. Note that braces have been used to make the body of the loop into a compound statement. Each time the loop is executed it is the instructions between the braces that are executed.
Hence the following version of the algorithm:

initialise.
get count of numbers.
if count is zero
   then exit
   otherwise {
              loop count times
                {
                 enter a number.
                 process the number.
                }
              output results.
             }

It has not yet been considered how to compute the maximum and minimum values so this has been indicated by using the phrase `process the number'. Given a large list of numbers written down on a sheet of paper how could the smallest number in the list be found in a methodical fashion? One way would be to start at the beginning of the list and work through the list systematically always remembering the smallest number seen so far, whenever a number is found smaller than the memorised number the memorised number is replaced by the smaller number. At the start of the list the smallest number yet seen is of course the first number, and when the end of the list is reached the memorised number is the smallest. Similarly for the largest number. Hence the following expansion:

get count of numbers.
if count is zero
   then exit
   otherwise {
              get first number.
              set small to number.
              set large to number.
              loop count-1 times
                {
                 enter a number.
                 if number is less than small
                    then set small to number.
                 if number is greater than large
                    then set large to number.
                }
              print small and large.
             }

In this algorithm no initialisation is required at the beginning, the only quantities that have to be initialised are small and large, and they are initialised to the first number entered by the user. Similarly count is entered by the user and requires no initialisation.

A brief reading of this should convince us that this algorithm is correct. If the user enters zero for the count then exit takes place immediately. If the user enters a non-zero count the first number is input, then the loop is executed count-1 times and one number is entered in each execution of the loop body. This means that 1 plus count-1 numbers are entered so all input numbers are considered. Large and small are initialised to the first number entered and each time round the loop are updated if the current number is larger or smaller than the memorised large or small. The boundary case where the count is zero has been considered but there is another boundary case here, namely count equal to one. If count is equal to 1 then large and small are set to the single number and the loop is executed zero times, hence when large and small are output they are set to the only number input, which is the correct result.

It is worth checking this algorithm by doing a simple desk check, say with the following data:

count = 5
numbers are 3 5 1 7 2
The different values taken during the algorithm are as follows:
count  number large small

 -       -      -     -     begin
 5       -      -     -     enter count
 5       3      3     3     enter first number
 5       5      5     3     first loop execution
 5       1      5     1     second loop execution
 5       7      7     1     third loop execution
 5       2      7     1     final loop execution

The symbol `-' has been used to indicate an unknown value. At the end of execution of the algorithm large and small do hold the correct maximum and minimum values


Next: Summary Up: Algorithms Previous: Desk-checking