Write a C program that will contain the following: Write a function that will ma

Question

Write 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 arrayCopy (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 sort (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 lsearch (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 bsearch (int arr[], int size, int target, int* numComparisons);

Inside of main:

read in integer input from standard input and store these values into an array.

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. The use of a scanf() with the following form is suggested to read in the values:

scanf (“%d”, &val);

make another array that will be large enough to hod all of the values read inand then copy of the integer array using the function copyArray() as described above

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

read in integer input from standard input and search for these values using both search functions described above (i.e. perform a linear search on the value in the unsorted array and perform a binary search on the value in the sorted array). Print out whether the value was found or not found and the number of comparisons needed to determine whether the value exists or not in each algorithm. 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.

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

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000 //define spot inside the arry no more than 1000
int binarySearch (int arr[], int size, int target, int* numComparisons)
{
int low =0;
int high = size-1;
int mid =(low+high)/2;
while(low<=high){
*numComparisons+=1;
if(arr[mid]<target)
low=mid+1;
else if (arr[mid]==target)
return mid;
else
high=mid-1;
mid =(low+high)/2;
}
if (low>high)
return -1;
}
int linear_search (int arr[], int size, int target,int* numCompare)
{
int i,found;
for (i=0; i<size; i++){
*numCompare+=1;
if (arr[i] == target){
return i;
}//end if
}//end for
return -1;
}
void swap ( int array[], int x, int y)
{
int NumberOfSwaps =0;
int temp = array[ x];
array[ x] = array[ y];
array[ y] = temp;
NumberOfSwaps++;   // increment number of swaps
}//end swap()
void selectionSort( int a[ ], int size)
{
int pass, j;
//printf( "Sorting using selection sort...");
for (pass = 0; pass < (size-1); pass++) {
// find smallest remaining value
int indexOfSmallest = pass;
for (j = pass+1; j < size; j++) {
if (a[ j] < a[ indexOfSmallest]) {   // Store new smallest value when found
indexOfSmallest = j;
}
}//end for ( int j...
// swap smallest element found on this pass into place
swap( a, pass, indexOfSmallest);
}//end for (int pass..
//printf( " ");
}
void arrayCoppy (int fromArray[], int toArray[], int size)
{
int index;
for(index=0; index<=size; index++)
{                             // loop from the 0 element to the rest
toArray[index]=fromArray[index];
// stored unsortArray value to a new copy one
}
return;                                             //return nothing
}
int main(){
int user_input;                         //user input
int unsortArray[MAX];                   //original unsorted array
int cppArray[MAX];                      //copied unsorted array
int Numcp=0; //howmany time it takes to get results
printf("please enter number to add in the array:");//promp user input
int i=0;                                //increment
int count=0;                             //counting size of the array
do {
scanf("%d", &user_input);
if (user_input != -999) {
unsortArray[count++] =user_input;
}
} while (user_input!= -999);
int j;
arrayCoppy(unsortArray,cppArray,count); // coppy the unsorted array to a new array
selectionSort(cppArray,count);
printf(" Please enter your number to search in unsorted array by linear search: ");
int target;
int found;
scanf("%d",&target);
found=linear_search(unsortArray,count,target,&Numcp);
if(found!=-1){
printf(" Target number %d has been found at location unsorted array[%d] ",target,found);
}
else {
printf(" The target does not exit in the array ");
}
printf("Numcompare=:%d ",Numcp);
printf(" These are sorted array ");
for(j=0;j<count;j++)
{
printf("%d:%d ",j,cppArray[j]);
}
printf(" Perform searching in sorted arry by binary search..... ");
int found2;
Numcp=0;
found2=binarySearch(cppArray,count,target,&Numcp);
if(found2!=-1){
printf(" Target number %d has been found at location arr[%d] ",target,found2);
}
else{
printf("The target does not exit ");
}
printf("Number of comparison:%d ",Numcp);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.