Question

Write one single program that does all of the following tasks, in order. You should practice proper Top Down Design and Procedural Abstraction techniques unless otherwise noted.

1. -Write a program with the following functions, with the correct number of arguments for each function.

-void fillUpArray ( argument1, argument2) This function should read in a text file called "villagers.txt" (You will create your own). "villagers.txt" is a text file of numbers in ascending order, ranging anywhere from 1 to 100, nonrepeating. Each number is separated by a new line character. The very first number in the text file is a number that refers to how many entries are in the rest of the text file. This function should populate an array with all the remaining entries in the text file, but it should NOT declare any arrays itself and it should not reference any global variables.

-void printArray (argument1, argument2) This function should print out the contents of an array, with a space between each item.

-any other functions used in class.

-You should use the concept of partially filled arrays by declaring an array of some arbitrarily large size, and having a variable "numberUsed" that will eventually store the number of values in the array. Do this in the main function, and then make the appropriate function calls to accomplish the following task:

       -After the array is populated, the program should then output the array and ask the user to input 2 numbers, one at a time, discarding all excess input. Other input validation is NOT needed. The program will then search the array (in an efficient manner) for these 2 numbers, swap their positions in the array, and output the new array. If either one of the numbers isn't in the array, the program should output an appropriate message instead.

The swapping of the two values MUST be done with a function call, and MUST be done with the mySwap function presented in class.

Example village.txt (the first number 7 means there are 7 additional numbers afterwards)

7

6

9

10

14

16

29

56

(Possible Correct Output)

The array is: 6 9 10 14 16 29 56

Enter a number to search for: 10

Enter another number to search for: 29

New Array: 6 9 29 14 16 10 56

Answer 1

Solution:

This Solution contains an Explanation to solve the problem, full c++ code, proper comments with code and

finally execution of the program for your better and full understanding.

Explanation:

Before going to the direct coding part, let's understand the approach to solve the problem.

First, create a village.txt file with valid data.

Once this is done then next read the file and parse file numbers into an array.

now take two inputs numbers and search these two numbers in the array.

One can search linearly but this will cost to O(n) time.

so Why not search numbers in lesser time.

since the array is sorted, Hence Use Binary Search to search the numbers in the sorted array.

This will cost to O(log N) time.

If both numbers are found then swap by taking the third variable.

Now let's see the whole code for better visualization.

village.txt:

7
6
9
10
14
16
29
56

C++ code:

searchAndSwap.cpp

#include <iostream>

#include <fstream>

using namespace std;

// binary search to get index

int binSearch(int arr[], int low, int high, int num) {

// check low <= high

if (low <= high) {

// middle index

int middle = (low + high)/2;

// check for num to match

if (arr[middle] == num){

return middle ;

}

// num is in left side

if (arr[middle] > num){

return binSearch(arr, low, middle-1, num);

}

// num is in right side

if (arr[middle] < num){

return binSearch(arr, middle+1, high, num);

}

}

// return for not found

return -1;

}

// swap the numbers in array

void mySwap(int arr[],int index1,int index2){

// temp var

int temp = arr[index1];

// replace index1 num with index2 num

arr[index1] = arr[index2];

// again replace index2 num with index1 num

arr[index2] = temp;

}

int main(int argc, char * argv[]){

// given file name

string fileName = "village.txt";

int n,i=-1;

int temp,num1,num2;

std::fstream fp(fileName, std::ios_base::in);

// read first integer, which is size of array

fp >> n;

// CREATING ARRAY

int arr[n];

while (fp >> temp){

arr[++i] = temp;

printf("\n%d", temp);

}

// print arr

cout<<"\nThe array is: ";

for(int i=0;i<n;i++){

cout<<arr[i]<<" ";

}

cout<<"\nEnter a number to search for: ";

cin>>num1;

cout<<"Enter another number to search for: ";

cin>>num2;

int index1,index2;

// search both number in sorted array

index1 = binSearch(arr,0,n-1,num1); // args: array,startIndex,endIndex,num

index2 = binSearch(arr,0,n-1,num2);

// check for found or not

if(index1 == -1){

cout<<endl<<num1<<" is NOT present in array";

}

if(index2 == -1){

cout<<endl<<num2<<" is NOT present in array";

}

if(index1 != -1 && index2 != -1){

// call func to swap the numbers

mySwap(arr,index1,index2);

}

// print the array

cout<<"\nNew Array: ";

for(int i=0;i<n;i++){

cout<<arr[i]<<" ";

}

// return from main func

return 0;

}

Screenshots:

This code is compiled and executed in terminal ubuntu 18.04.

E Solution: Untitled-2 • Solution: Untitled-1 G searchAndSwap.cpp X main(int,char * []), village.txt home > jay > HomeworkLib > C searchAndSwap.cpp > #include <iostream> #include <fstream> 3 using namespace std; village.txt x home > jay > HomeworkLib > 1 7 2 6 3 9 5 00 VOUW 14 16 29 56 // binary search to get index int binSearch(int arr[], int low, int high, int num) { // check low <= high if (low <= high) { // middle index int middle = (low + high)/2; // check for num to match if (arr[middle] == num) { return middle ; jay@jay: -/HomeworkLib File Edit View Search Terminal Help jay@jay:/ HomeworkLib$ g++ searchAndSwap.cpp jay@jay:-/HomeworkLib$ ./a.out // num is in left side if (arr[middle] > num) { return binSearch(arr, low, middle-1, num); // num is in right side if (arr(middle) < num) { return binSearch(arr, middle+1, high, num); 56 The array is: 6 9 10 14 16 29 56 Enter a number to search for: 10 Enter another number to search for: 29 // return for not found return -1; New Array: 6 9 29 14 16 10 56 jay@jay:~/HomeworkLib$ | 27 // swap the numbers in array void my Swap(int arr[], int indexl, int index2){ // temp var int temp = arr[index1]; // replace indexl num with index2 num arr[index1] = arr[index2]; // again replace index2 num with indexl num arr[index2] = temp; Ⓡ0AO Ln 80, Col 23 Spaces: 4 UTF-8 LF C++ Linux

G searchAndSwap.cpp X main(int,char * []), village.txt E Solution: Untitled-2 • E Solution: Untitled-1 home > jay > HomeworkLib > 6 searchAndSwap.cpp > #include <iostream> #include <fstream> 3 using namespace std; village.txt X home > jay > HomeworkLib > 1 7 2 6 3 9 5 5 6 7 8 14 16 29 56 // binary search to get index int binSearch(int arr[], int low, int high, int num) { // check low <= high if (low <= high) { // middle index int middle = (low + high)/2; // check for num to match if (arr[middle] == num) { return middle ; - OX jay@jay: -/HomeworkLib Search Terminal Help File Edit View // num is in left side if (arr[middle] > num) { return binSearch(arr, low, middle-1, num); 29 // num is in right side if (arr(middle) < num) { return binSearch(arr, middle+1, high, num); 56 The array is: 6 9 10 14 16 29 56 Enter a number to search for: 10 Enter another number to search for: 29 New Array: 6 9 29 14 16 10 56 jay@jay:-/HomeworkLib$ ./a.out // return for not found return -1; 27 29 // swap the numbers in array void my Swap(int arr[], int indexl, int index2){ // temp var int temp = arr[index1]; // replace indexl num with index2 num arr[index1] = arr[index2]; // again replace index2 num with indexl num arr[index2] = temp; 56 The array is: 6 9 10 14 16 29 56 Enter a number to search for: 6 Enter another number to search for: 23 23 is NOT present in array New Array: 6 9 10 14 16 29 56 jay@jay:-/HomeworkLib$ A Ln 6, Col 3 Spaces: 4 UTF-8 LF Plain Text Ⓡ0AO

Since everything is provided for your complete understanding,

However, if any queries regarding this problem then don't hesitate to ASK. I will surely answer you.