Linear search times

The main problem with the two search algorithms above is the fact that, no matter what, they may search through the entire array, without finding a value. If you change the value of MAX in program five, to 200,000, and at the prompt enter a number you know is not in the file, you will get a search time of around fifty-five seconds, this is what is called the not in array time. That is how long the program runs before it reports to the user that the searched for value does not exist in the supplied data. So the problem exists therefore, that both these search algorithms must search through the entire array before coming to that conclusion. Imagine therefore, that if we could put the data into an array in order so that a string beginning with 'A' came before one beginning with 'Z', and ones beginning with an 'a' came before one beginning with a 'z'. The if we were searching using a WHILE loop for the string value 'Steinbeck', the exit condition could include a statement to the effect that if the key field had an ASCII value greater that the searched for string. Then the possible position for that string had been passed, and therefore the value did not exist in the array. To continue with the search would be pointless, and so exit from the loop, and report the not found result. Because each character has its own unique ASCII value it is possible to compare strings in the same way as numbers are compared to each other.
For example:

• Apple is less than Banana.
• Smith is greater than Jones.
• 100 is less that 200.
• 12345 is less than 43214.

So how do we arrange to have these ordered arrays in Pascal? Well, after the data is stored into the array we must first use a sorting algorithm, before we perform the search algorithm.

Sorting an array

The main objective of sorting an array is to reduce the not in array time of a linear search, a linear search is when the algorithm starts searching from one end and inspects each element, before going on to inspect the very next element. The average found in array time remains the same whether the array is sorted or not. As long as the values are properly distributed. I mean by this if you only search through an array for a low value and all the low values are bunched up at either end, then the found in array time will be small or large, but if all the values are fairly well spread out then the average found in array time for the entire range of values will will be roughly the same. The first sorting algorithm we will look at is called selection sort. As we already know, in order to search through a data-structure such as a string or an array we need a loop. In selection sort, we actually need two loops. We always know the size of the array, and we should always know the number of elements which have been loaded with a value. So a FOR loop would seem to fit the bill, since we will want to examine every single element of the array. In the initial condition of selection sort, the first FOR loop's control variable is set at 1, and the second FOR loop's control variable is set to that same value plus 1.

Date: 2016-03-03; view: 633