Fall 2013
Programming Project 3
Due: Thursday, 9/312/13 at 11:59 pm
Write a 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 a copy of the integer array using the function 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. Loop for integer values 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 assume the input will never have more than 1000 values to store in the array.
#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( "\n");
}
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("\nPlease enter your number to search in unsorted array by linear search:\n");
int target;
int found;
scanf("%d",&target);
found=linear_search(unsortArray,count,target,&Numcp);
if(found!=-1){
printf("\n\nTarget number %d has been found at location unsorted array[%d]\n",target,found);
}
else {
printf("\nThe target does not exit in the array\n");
}
printf("Numcompare=:%d\n",Numcp);
printf("\nThese are sorted array\n\n");
for(j=0;j<count;j++)
{
printf("%d:%d\n",j,cppArray[j]);
}
printf("\nPerform searching in sorted arry by binary search.....\n\n");
int found2;
Numcp=0;
found2=binarySearch(cppArray,count,target,&Numcp);
if(found2!=-1){
printf("\nTarget number %d has been found at location arr[%d]\n",target,found2);
}
else{
printf("The target does not exit\n");
}
printf("Number of comparison:%d\n",Numcp);
return 0;
}
No comments:
Post a Comment