CS211-Project 1 Solved

Write a C program (not a C++ program!) that will contain the following:

 

•        Write a function that will make a copy the values from one array to another array.  Suggested prototype:   

void makeArrayCopy (int fromArray[], int toArray[], int size);

 

•        Write your own function that will sort an array in ascending order.  You may use whatever sorting algorithm you wish.  Suggested prototype:   

void myFavorateSort (int arr[], int size);

 

•        Write your own function that will perform a linear search on the unsorted array.  The function is to “return” two values.  The first should be the position in the array where the value was found or -1 if the value was not found.  The second is the number of comparisons needed to determine if/where the value is located in the array.   Suggested prototype:

int linSearch (int arr[], int size, int target, int* numComparisons);

 

•        Write your own function that will perform a binary search on the sorted array.  The function is to “return” two values.  The first should be the position in the array where the value was found or -1 if the value was not found.  The second is the number of comparisons needed to determine if/where the value is located in the array.  Suggested prototype:

int binSearch (int arr[], int size, int target, int* numComparisons);

 

Inside of main:  

•        read in integer input from standard input and store these values into a dynamic array.  This array is to grow in size if the array is full.  The values will have a “terminal value” of -999.  So you read in these values in a loop that stops when the value of -999 is read in.  The use of informative prompts is required for full credit.  You may not assume how many numeric values are given on each line, nor the total number of values contained in the input.  The use of a scanf() with the following form is expected to read in the values:

scanf (“%d”, &val);  

 

•        make a copy of the integer array using the arrayCopy() function described above

 

•        sort one of the arrays (using the myFavoriteSort() function described above), leave the other array unsorted

             

Inside of main (continued):

•        read in integer input from standard input (again, the use of scanf() is expected) and for each of the values read in search for the value using both search functions described above (i.e. for each value read in, perform a linear search on the unsorted array and perform a binary search on the sorted array).   Using the information returned/sent back from the search functions, print out from main():

 

1.     The value being searched for and the type of search being preformed.

2.     Whether the value was found or not found,

3.     The number of comparisons needed to determine whether the value exists or not in each algorithm,

4.     And the location in the array where the number is located (if the value does exist in the array).   

 

The above information MAY NOT be printed out in the linear search or binary search functions.  Those functions MUST RETURN/SEND BACK the information to be printed by the main function.  Not doing this will SEVERELY LOWER your score on this project. 

 

Repeat reading in integer values and searching the arrays until the terminal value of -999 is read in.  The use of informative prompts AND descriptive result output is required for full credit.  Again, scanf() is expected to read the input.

 

You may not assume the input will be less than any set size.  Thus you will need to dynamically allocated space for the array.   

 

Dynamic Array Allocation
 

Dynamic Array Allocation allows the space in an array to change during the course of the execution of a program.  In C, this requires the use of the malloc() function.  To dynamically allocate space for 100 integers, the malloc() code would be as follows:

 

            int *darr;

           int allocated = 100;

            darr = (int *) malloc (allocated * sizeof(int) );  

 

This array can only hold 100 integers and it not really dynamic.  To make it truly dynamic, we need to grow the array when we try to put more values into it than can be held by its current size.  The following code will double the size of the array.

 

            int *temp = darr;

            darr = (int *) malloc ( allocated * 2 * sizeof(int) );

            int i;

           for ( i = 0 ; i < allocated ; i++)

                        darr[i] = temp[i];           free (temp);

            allocated = allocated * 2;

 

             

Running your C Program (not a C++ program) 

 

Make sure your program runs properly when compiled using gcc on the bert.cs.uic.edu machine!  (Do not use g++ or any other C++ compiler with this program.)

 

Programming Style
Make sure your program is written in good programming style.  This includes but is not limited to:

•        In-line commenting

•        Function header commenting

•        File header commenting

•        Meaningful and description variable names

•        Proper use of indentation  

•        Proper use of blank lines

•        Use of Functions