Hello ppl.
Ok have to investigate and write a report on the efficiency of the following Linear Search algorithm.
But im having problems starting off.... can anyone here help me kick start this 3 page report... would apreciate any information & help you guys here can give.
// This program randomly generates a series of test data of
// differing sizes
// (5 - 100 positive integers) reading them into array a.
// It then randomly generates a search key
// and searches the elements of the array using linear search.
// It returns a table giving the amount of data the test was
// run on and the number of comparisons made.
#include <stdlib.h>
// Make standard library available eg for random number
// generation functions
#include <stdio.h> // Make input/output library available
#include <time.h>
// define a new type called SearchResult
//(like int is already a type)
//There are two values (like 1, 2,3 etc are values for ints)
// of type searchResult: FOUND and NOT_FOUND
enum SearchResult {FOUND, NOT_FOUND};
// List the functions in this program
SearchResult linearSearch
(int array[], int key, int sizeOfData, int *comparisons);
void fill_array(int array[], int sizeOfData);
const int RANGE = 200; // random data used in range 0-199
int main()
{
const int arraySize = 100;
int a[arraySize];
FILE *resultsFile;
resultsFile = fopen("lsrch.dat", "w");
// open the file lsrrch.dat for writing ("w")
if (resultsFile != NULL) // file successfully opened
{
// seed the random number generator so it gives different
// random numbers each time
srand ( time (0) );
// Table headings
printf ("Found\t Data Size\t Comparisons Needed\n" );
//\t puts in a tab character, \n a new line
fprintf(resultsFile,"Data Size\t Comparisons Needed\n");
// Generate table for data of different sizes
// giving number of comparisons each time
for (int datasize = 1; datasize <= arraySize; datasize = datasize+1)
{
int count = 0; // number of comparisons this time
SearchResult result; // result of this search
int searchKey = rand() % RANGE;
fill_array(a, datasize);
result = linearSearch(a, searchKey, datasize, &count);
// Note address of count passed - so by reference
if (result == FOUND)
printf("KEY FOUND \t");
else
printf("NOT FOUND \t");
// print results in a table
printf("%d \t\t\t %d\n", datasize, count);
fprintf(resultsFile, "%d \t\t\t %d\n", datasize,count);
}
}
else
fprintf(resultsFile, "File not opened\n");
fclose(resultsFile); return 0;
}
// generate random data in range 0-20 and fill the
// array with it up to the given size
void fill_array(int array[], int sizeOfData)
{
for (int counter = 0; counter < sizeOfData; counter++)
{
array[counter] = rand () % RANGE;
}
}
// A linear search function that returns the number of
// comparisons
// call by value as well as a direct indication of found or not.
SearchResult linearSearch
(int array[], int key, int sizeOfData, int * comparisons)
{
*comparisons = 0; // count comparisons made
//Note comparisons passed by reference so use * to refer
//to value at that address
for (int counter = 0; counter < sizeOfData; counter++)
{
*comparisons = *comparisons + 1;
//about to do a comparison
if (array[counter] == key)
return FOUND; // Key found!
}
return NOT_FOUND; // Key not found
}
Again i would apreciate all help.
Thanks
Peace!!