Skeleton for Assignment 2 // dynalloc parms: array size, pointer to array which

Question

Skeleton for Assignment 2

// dynalloc parms: array size, pointer to array which is defined in main but modified by function when it executes the // definition with “new.” Return value: none.

void dynAlloc(int, int*&);

// insertionSort parms (or bubbleSort parms): pointer to array to sort, array size, pointer to sorted array. // Return value: number of iterations.

int insertionSort(int *, int, int *);

// linearSearch parms: pointer to array to search, array size, target value, number of iterations. Number of
// iterations defined in main but modified by search. Return value: element # of found element, or -1 if not found.

int linearSearch(int *, int, int, int &);
// binarySearch parms: same as with linearSearch int binarySearch(int *, int, int, int &);
main

numElements=100;
int * unsortedArrayPtr, * sortedArrayPtr;

dynAlloc(numElements, unsortedArrayPtr) for(i=0;i<100;i++)

unsortedArrayPtr[i]=rand() % 100+1 cout ... unsorted array

dynAlloc(numelements, sortedArrayPtr) numIter=insertionSort(unsortedArrayPtr, numElements, sortedArrayPtr) cout ... sorted array
cin ... a target value
while (!= -1)

return

// don’t forget to clean up

// new not xeq’d until execution time

wasFound=linearSearch(sortedArrayPtr, numElements, targetValue, numIter) cout ... results
wasFound=binarySearch(sortedArrayPtr, numElements, targetValue, numIter) cout ... results

cin ... a target value

dynAlloc(int numelements, int * &ptrtothearray) ...

ptrtothearray=new int[numelements]

int insertionSort(int *toSort, numElements, int*sortedResult) ...

sortedResult[i]=toSort[i]; ...

// or use a global
// a ptr can function as an array name – it can be subscripted // refer to the “rules”
// get space for array to sort
// populate array to sort

// get array to hold sorted result

if (sortedResult[i] < sortedResult[i-1]) ...

int linearSearch(int *toSearch, numElements, targetValue, numIterations) ...

if(toSearch[i] = targetValue) ...

int binarySearch(int *toSearch, numElements, targetValue, numIterations) ...

if(toSearch[i] = targetValue) ...

In assignment 2, you'll have main use dynAlloc to get space for the two arrays, one array at a time, and two new functions which both search the array for a given value. You'll also reuse one of your sort functions from assignment 1. You'll have a main which will now look like: invoke dynAlloc to get space for the unsorted array populate the unsorted array with random integers display the unsorted array invoke dynAlloc to get space for the sorted array invoke a sort function display the sorted array get an integer from the user at the console loop while the user integer is non-negative invoke linearSearch display the result(s) invoke binarySearch display the result(s) get another integer from the user exit Function dynAlloc The dynamic allocation function has two arguments - the number of elements to allocate, and a pointer to the allocated array. Use 100 as the number of elements. The pointer is defined in main and passed by reference so that when the function allocates the array, the pointer can be passed back to main. The function uses the "new" operand to allocate the array. Functions linearSearch and binarySearch

Explanation / Answer

If you have any doubts, please give me comment...

#include <iostream>

#include <cstdlib>

using namespace std;

// dynalloc parms: array size, pointer to array which is defined in main but modified by function when it executes the // definition with “new.” Return value: none.

void dynAlloc(int size, int *&arr)

{

arr = new int[size];

}

// insertionSort parms (or bubbleSort parms): pointer to array to sort, array size, pointer to sorted array. // Return value: number of iterations.

int insertionSort(int *arr, int size, int *sort_arr)

{

int i, key, j, no_iterations = 0;

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

sort_arr[i] = arr[i];

for (i = 1; i < size; i++)

{

no_iterations++;

key = sort_arr[i];

j = i - 1;

while (j >= 0 && sort_arr[j] > key)

{

no_iterations++;

sort_arr[j + 1] = sort_arr[j];

j = j - 1;

}

sort_arr[j + 1] = key;

}

return no_iterations;

}

// linearSearch parms: pointer to array to search, array size, target value, number of iterations. Number of

// iterations defined in main but modified by search. Return value: element # of found element, or -1 if not found.

int linearSearch(int *arr, int size, int x, int &iterations)

{

iterations = 0;

for (int i = 0; i < size; i++)

{

iterations++;

if (arr[i] == x)

return i;

}

return -1;

}

// binarySearch parms: same as with linearSearch int binarySearch(int *, int, int, int &);

int binarySearch(int *arr, int size, int x, int &iterations)

{

int l = 0, r = size - 1;

iterations = 0;

while (l <= r)

{

iterations++;

int m = l + (r - l) / 2;

if (arr[m] == x)

return m;

if (arr[m] < x)

l = m + 1;

else

r = m - 1;

}

return -1;

}

int main()

{

int numElements = 100;

int *unsortedArrayPtr, *sortedArrayPtr;

dynAlloc(numElements, unsortedArrayPtr);

for (int i = 0; i < 100; i++)

unsortedArrayPtr[i] = rand() % 100 + 1;

cout<<"Unsorted array: "<<endl;

for (int i = 0; i < numElements; i++)

{

cout << unsortedArrayPtr[i] << " ";

}

cout << endl;

dynAlloc(numElements, sortedArrayPtr);

int numIter = insertionSort(unsortedArrayPtr, numElements, sortedArrayPtr);

cout<<"Sorted array: "<<endl;

for (int i = 0; i < numElements; i++)

{

cout << sortedArrayPtr[i] << " ";

}

cout << endl;

int targetValue;

cout << "Enter search value: ";

cin >> targetValue;

while (targetValue >= 0)

{

// don’t forget to clean up

// new not xeq’d until execution time

int wasFound = linearSearch(sortedArrayPtr, numElements, targetValue, numIter);

cout<<endl<<"Using linear Search: "<<endl;

if (wasFound != -1)

cout << "Target found at location : " << wasFound << " and takes " << numIter << " iterations." << endl;

else

cout << "Target not found" << endl;

cout<<endl<<"Using binary Search: "<<endl;

wasFound = binarySearch(sortedArrayPtr, numElements, targetValue, numIter);

if (wasFound != -1)

cout << "Target found at location : " << wasFound << " and takes " << numIter << " iterations." << endl;

else

cout << "Target not found" << endl;

cout << "Enter search value: ";

cin >> targetValue;

}

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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