The overall goal of this C program is to: 1. Read in a list of integers from standard input and store those values into an array. (Stop reading the input when the value of -999 is read in.) 2. Make a copy of that array 3. Sort the copy of the array 4. Read in a second list of integers from standard input (again stop reading the input when the value of -999 is read in). For each integer: a. Do a linear search on that value in the unsorted array b. Do a binary search on that value in the sorted array c. Print out the following information from each search: i. Was the value found or not found? ii. How many comparisons were needed to determine if it was found or not iii. If found, in what position was the value found in each array The values read in by the program will form 2 lists of integers. Each list of values will end with the terminal value of -999. You can assume that the values will only be integer values and that there will be two values of -999 in the input. For example, assume the data entered was as follows: 3 9 57 18 2 4 -999 57 18 3 -999 The first 6 values would be stored in the array (3, 9, 57, 18, 2, 4). The searches would be done using the values of 57, 6, 18 and 3. 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. You are required to use this function when making the copy of the array (see item #2 above). Suggested prototype: void arrayCopy (int fromArray[], int toArray[], int size); Write your own function that will sort an array in ascending order. You are required to use this function when sorting one of your arrays (see item #3 above). You may use whatever sorting algorithm you wish. Suggested prototype: void myFavorateSort (int arr[], int size);

CODE:-

#include <stdio.h>
#include <stdlib.h>

void arrayCopy(int fromArray[], int toArray[], int size);
void sort(int arr[], int size);
int linSearch(int arr[], int size, int target, int* numComparisons);
int binSearch(int arr[], int size, int target, int* numComparisons);

//Main Program

int main(){
        int size = 100; 
        int inputArr1 = (int)malloc(size*sizeof(int));
        int *copied_array, *inputArr2;
        int i, numComparisons, position;
        int element, currentSize1, currentSize2;

        currentSize1 = 0;

        scanf("%d", &element);

        //reading input for first array until user enters -999
        while(element != -999){
                inputArr1[currentSize1] = element;              
                currentSize1++;

                if(currentSize1 == 100){
                        inputArr1 = realloc(inputArr1, 2*size*sizeof(int));
                        size *= 2;
                }

                scanf("%d", &element);
        }

        copied_array = (int*)malloc(currentSize1*sizeof(int));

        //copying the content of inputArr1 to copied_array 
        arrayCopy(inputArr1, copied_array, currentSize1);

        //sorting the copied array
        sort(copied_array, currentSize1);

        currentSize2 = 0;
        size = 100;

        inputArr2 = (int*)malloc(size*sizeof(int));

        scanf("%d", &element);
        //reading input for second array for target elements until user enters -999
        while(element != -999){
                inputArr2[currentSize2] = element;              
                currentSize2++;

                if(currentSize2 == 100){
                        inputArr2 = realloc(inputArr2, 2*size*sizeof(int));
                        size *= 2;
                }

                scanf("%d", &element);
        }

        //displaying sorted array
        printf("\nSorted Array formed: ");
        for(i=0; i<currentSize1; i++){
                printf("%d ", copied_array[i]);
        }

        //displaying all details for each target element in inputArr2
        for(i=0; i<currentSize2; i++){

                numComparisons = 0;

                printf("\n\nUsing Linear Search:");
                position = linSearch(inputArr1, currentSize1, inputArr2[i], &numComparisons);
                if(position != -1){
                        printf("\nElement %d found at position %d in the unsorted Array.\n", inputArr2[i], position);
                        printf("Number of Comparisons needed = %d\n", numComparisons);
                }
                else{
                        printf("\nElement %d not found, but number of comparisons performed = %d\n", inputArr2[i], numComparisons);
                }

                numComparisons = 0;

                printf("\nUsing Binary Search:");
                position = binSearch(copied_array, currentSize1, inputArr2[i], &numComparisons);
                if(position != -1){
                        printf("\nElement %d found at position %d in the sorted Array.\n", inputArr2[i], position);
                        printf("Number of Comparisons needed = %d\n", numComparisons);
                }
                else{
                        printf("\nElement %d not found, but number of comparisons performed = %d\n", inputArr2[i], numComparisons);
                }
        }

        //deallocating all dynamically allocated memory
        free(inputArr1);
        free(copied_array);
        free(inputArr2);

        return 0;
}

//Function Definitions

//copies elements of fromArray[] to toArray[]   
void arrayCopy(int fromArray[], int toArray[], int size){
        int i;
        for(i=0; i<size; i++){
                toArray[i] = fromArray[i];
        }
}

//implementing bubble sort algorithm
void sort(int arr[], int size){
        int i,j;
        int temp;

        for(i=0; i<size; i++){
                for(j=0; j<size-1-i; j++){
                        if(arr[j] > arr[j+1]){
                                temp = arr[j];
                                arr[j] = arr[j+1];
                                arr[j+1] = temp;
                        }
                }
        }
}

//implements linear search and returns position of target  if found, else -1
//also find and store number of comparisons needed to find the target
int linSearch(int arr[], int size, int target, int* numComparisons){
        int i;

        for(i=0; i<size; i++){
                (*numComparisons)++;
                if(arr[i] == target){
                        return i+1;            //since position = index + 1
                }
        }

        return -1;   //if element not found
}

//implements binary search and returns position of target  if found, else -1
//also find and store number of comparisons needed to find the target
int binSearch(int arr[], int size, int target, int* numComparisons){
        int i,j,mid;

        i = 0;
        j = size-1;

        while(i<=j){

                mid = (i+j)/2; 

                (*numComparisons)++;
                if(arr[mid] == target){
                        return mid+1;         //since position = index + 1
                }

                else if(arr[mid] < target){
                        i = mid + 1;
                }

                else{
                        j = mid - 1;
                }
        }

        return -1;
}