ALGORITHMS
There are many tasks in programming that are done many times (including sorting and searching). So instead of having to start from scratch, you can use existing standard logic for those tasks (and in many languages now you don’t even need to code this logic but simply use existing standard modules or library routines).
The logic of the standard algorithms can vary slightly. How the logic is then implemented can also vary depending upon the language used.
Many of the standard algorithms listed apply to arrays, so some basic information about arrays is needed to be able to explain the standard algorithms.
Finding maximum and minimum values in arrays
Finding a Maximum value
There are three parameters required: an array of items, a start index and a stop index.
Standard logic / Algorithm description of standard logicGiven an unsorted indexed array
- Need a variable to hold the index of the max value (this index will not hold the max value but hold the index of the max value)
- Set the max index variable to the index of first element in the array
- Check each consecutive element in the array to see if is larger than the current max value held. If it is change the max index variable to the index of that element
- When the end of the array is reached, the max variable will hold the index of the largest value
maxindex = 1
count = 0
WHILE not end of array
count = count + 1IF Array(count) > Array(maxindex) THEN
maxindex = count
ENDIF
ENDWHILE
PRINT Array(maxindex)
END
So now you have the standard logic for finding a maximum value you can apply it to an example.
An example of a search for maximum values using a pretest loop can be used to demonstrate the process of desk checking the algorithm. The array name is given, the search criteria and the elements in an array of three items.
Array name: / Reals / Search criteria: MaxIndex / 0 / 1 / 2
Data / 1.2 / 1.3 / 1.1<
BEGIN FindItem /
Index=0 / 0
Get search (Max or Min) / Max
If Search=Max THEN /
Max=0 / 0
ELSE
Min=Array(0)
Index=Index+1
ENDIF /
WHILE more array items / / / / X
FindValue / Called
Returned 1.2 / Called
Returned 1.3 / Called
Returned 1.3
Index=Index+1 / 1 / 2 / 3
ENDWHILE / X
Display value and location / 1.3, Reals(1)
ENDFindItem /
BEGIN FindValue
If Search=Max THEN / / /
IF Array(Index)>Max THEN / / / X
Max=Array(Index) / 1.2 / 1.3
ELSE IF Search=Min THEN / X
IF Array(Index)<Array(Min) THEN
Min=Array(Index)
ENDIF / /
ENDIF / /
ENDIF / /
ENDIF / /
END FindValue / / /
Processing strings (extracting, inserting, deleting)
Strings are data types that hold a number of characters together (e.g. a string of 10 characters). There is standard logic for extracting data from a string and inserting and deleting characters (in some programming languages this logic has been replaced by library functions within the program, which enable you just call the function rather than actually coding the logic).
Three of the more useful procedures in the manipulation of strings include:
- Extraction, or removing strings or characters from a string for use in other strings. This is equivalent to the copy command in a word processor where the characters to be extracted are removed while leaving the original characters intact.
- Insertion, or placing strings or characters into a string. This is equivalent to the paste command in a word processor where the characters to be inserted are placed into position in the existing string.
- Deletion, or removal of strings or characters from a string. This is equivalent to the cut command in a word processor where the characters to be inserted are placed into position in the existing string.
E.g. Deleting a character from an array. If you had a string of characters and you wanted to delete one of the characters from the middle then you had to create this logic.
Standard logic / Algorithm description of standard logic- Locate character to be deleted
- Move all character to the right of this character one position to the left one at a time until the end of the string is reached
Locate position of the character to delete
WHILE not end of string
Move string(position+1) to string (position)
position = position + 1
ENDWHILE
Eg A desk check of an algorithm that is extracting data from a string.
Index / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11Data / J / o / n / a / A / . / D / o / e / .
The surname (Doe) needs to be extracted (copied) for use in another list. The last character (.) is not required. The original list is left intact
What this means … We want to copy the data starting at position 8 and the three letters following this – ie we want to copy the word Doe and store it in a variable called “Data”. The algorithm shown below is a snippet from a sub-routine … ie it assumes that a main program will pass the parameters to it – namely : the start position of the word we want, the length of the word we want and the name of the array where we will find the data.
However, in our BASIC example we wont bother with all this.
Some BASIC like code follows
REM Here is some data to work with
DATA H,e,l,l,o, ,k,i,t,t,y
REM We need to declare the array otherwise BASIC will complain
DIM textarray(12) as string
REM Now we need to put the data into the array
FOR t = 1 to 11
Read textarray(t)
Next t
REM Now print it back (echo) so we know it works
FOR t = 1 to 11
PRINT textarray(t);
Next t
REM Ok, now we need to ask the user where to start copying from and how many letters to copy.
Input “Start location “;start
Input “How many letters “;howmany
REM Now we copy the data (assume we magically know there is only 11 letters in the text)
Findtext$ = “”
For t = start to start + howmany
Findtext$ = Findtext$ + textarray(t)
Next t
REM Ok, done … now echo the result
PRINT “ The word you were looking for was “;findtext$
BEGIN ExtractString (8,3,Data)Temp=””
Index=Start / 8
Character= / 0
WHILE Characters<Length / / / / X
Temp=Temp+Data(Index) / D / Do / Doe
Index=Index+1 / 9 / 10 / 11
Length=Length-1 / 2 / 1 / 0
ENDWHILE /
Data=Temp / Doe
END ExtractString /
File Processing, including sentinel value
An example of this is where data (records) are copied (read) from a sequential data file (secondary storage) into an array (primary storage) for use by the program.
Another name for a sentinel value is a dummy value. The value needs to be chosen so it will not be confused with an acceptable input value.
An example of a sentinel value is an end of file (EOF) character, which is at the end of a data file. The sentinel value is used to signal the end, in this case, the end of data in the file.
E.g. File processing to get data from a data file into an array.
Standard logic / Algorithm description of standard logic- Set file to read and to first data item
- While data in the file is not the EOF character continue
- Copy the data item in the file to the array
- Move to next data item. and increment array
- repeat point 2
index = 0
WHILE NOT EOF
index = index + 1
Array(index) = data at current position in file
Get next item in fileENDWHILE
Using file input and output requires specific procedures in each programming language. Such programs need an additional parameter defining which file to use for input or output, and the parameter is also language specific.
Processing a file can be shown in the following algorithm that reads a file called Terms. The file is a sequential file stored as sets of data composed of two lines: the first line contains a term and the second line provides a simple definition of the term. The program using the file uses two text structures called Position 1 and Position 2 to display the output from the file. Position 1 holds the terms and Position 2 holds the definitions. A simple example of the file with two sets can be shown as:
Algorithm
A finite set of sets required to solve the problem
File
A collection of data of various types stored as a single unit.
The algorithm is written to read the data into a program from the file Terms.
BEGIN ReadFile /Open file terms /
LineNo=1 / 1
WHILE not EOF / / / X
Read LineNo / Algorithm / File
Write to Position 1 / Algorithm / File
LineNo=LineNo+1 / 2 / 4
Read LineNo / A finite set of steps required to solve a problem / A collection of data various types stored as a single unit
Write to Position 2 / A finite set of steps required to solve a problem / A collection of data various types stored as a single unit
LineNo=LineNo+1 / 3 / 5
ENDWHILE /
Close file Terms /
END ReadFile /