C++

You job is write the selection sort function and print the array before sorting and after sorting so we can see the differences. A partially done program is given to you. The program will read 20 randomly generated numbers from a file and put them into an array, prizeNumbers. The program will then sort the prizeNumbers. The program will also ask the user to guess a number and find out (using binary sort) if the number is in the list. If the number is not in the list, the program will continue prompt the user for another input number until either a correct number is entered or -1 is entered. The binary sort is implemented for you. Please trace the code and try to understand it. Your job is finish 1. The buildList() function and test it out. 2. The sortList() function and test it out. 3. Modify the binarySearch() function so that it will print out the number of comparisons used in the binarySearch() function. The output should say **** 5 Comparisons from BinarySeach ****, where 5 is the actual number of comparisons. Submit your program to the Blackboard.

PrizeList.txt

42 468 335 1 170 225 479 359 463 465 206 146 282 329 462 492 496 443 328 437

CreateList.cpp

#include

#include

using namespace std;

int main()

{

ofstream outData;

outData.open("prizelist.txt");

for (int count = 0; count < 20; count++)

outData << rand()%500 + 1 << endl;

return 0;

}

radioPrizeSort

// Enter your name as a comment for program identification

// Program assignment Prize.cpp

// Enter your class section, and time

/* The program Prize.cpp simulates a radio station that

asks the caller to guess a number. The number is

compared against a list of 20 numbers between 1

and 500 inclusive. The contest is held until a number

has been matched or a value of -1 is entered.

A message is displayed containing the winning number,

the location in the list of numbers, the number of

calls made, and the amount of the prize. */

/* An input file PrizeList.txt is used to enter the data. */

/* A message is displayed containing the winning number,

the location in the list of numbers, the number of

calls made, and the amount of the prize. */

//header files

/* use the correct preprocessor directives for

input/output and file stream */

#include

#include

using namespace std;

// function prototypes

/* The function instruct describes the use and purpose of the program. */

void instruct();

/* The function openFile opens the data file */

//void openFile(ifstream &);

/* The function buildList reads the file and

assigns the values to an array. */

// *** function prototype for buildList goes here

/* The function caller prompts the user for a number */

int caller();

/* The function checkList checks the number input by the caller to the list. */

bool checkList(int [], int, int, int);

int binarySearch(int [], int, int, int);

/* The function displayPrize displays the prize won. */

void displayPrize(int, int, int);

// *** function prototype for sortList goes here

void printList(int [], int);

const int LIST_SIZE = 20; //a constant integer listSize initialized 20

int main() {

// declare variables

/* an integer array prizeNumbers of size LIST_SIZE,

an integer guess intialized to 1 to hold the user's guess,

an integer variable numberGuesses initialized to 0 to count the number of

guesses made, and

a Boolean variable found initialized to false to determine if the number

is found on the list.

*/

int prizeNumbers[LIST_SIZE], guess = 1, numberGuesses = 0;

bool found = false;

int foundPos = -1;

// call the function instruct

instruct();

// call the function buildList

buildList(prizeNumbers, LIST_SIZE);

cout << " ***** Before sort **** ";

printList(prizeNumbers, LIST_SIZE);

sortList(prizeNumbers, LIST_SIZE); // sort the list in ascending order

cout << " ***** After **** ";

printList(prizeNumbers, LIST_SIZE);

/* loop until a guess matches the list or the user enters -1 */

while (!found && guess > 0) {

// increment the number of guesses

numberGuesses++;

/* assign to guess the value returned from the function caller */

guess = caller();

/* if guess is greater than 0, call the function checkList */

if (guess > 0)

foundPos = binarySearch(prizeNumbers,0,LIST_SIZE - 1, guess);

if (foundPos != -1) {

found = true;

displayPrize(numberGuesses, foundPos, guess);

}

else

cout << guess << " is not in the list. Call again. ";

}

system("pause");

return 0;

}

/* The function instruct describes the use and purpose of the program. */

void instruct() {

cout << "This program simulates a radio station "

<< "that asks the caller to guess a number. "

<< "The number is compared against a list of "

<< "20 numbers between 1 and 500 inclusive. "

<< "The contest is held until a number has been "

<< "matched or a value of -1 is entered. A "

<< "message is displayed containing the winning "

<< "number, the location in the list of numbers, "

<< "the number of calls made, and the amount of "

<< "the prize. ";

}

// function buildList

void buildList(int prizeNumbers[], int listSize) {

// ****** your code for build the list into an array goes here *****

/* define an ifstream variable inData to read in the list of numbers */

// open the file

// check to see if the file opened

/* loop until all values in the list have been read */

// close the data file

}

/* The function caller prompts the user for a number */

int caller() {

// declare variables

// an integer guess to enter the user's guess

int guess;

// prompt the caller to enter a value

cout << "Hello Caller. What number between 1 and 500 are you guessing? ";

// enter the value

cin >> guess;

// check to see if the user entered -1 to quit

if (guess == -1)

return guess;

// check to see if the guess is within bounds

if (guess < 1 || guess > 500)

cout << "Your guess must be between 1 and 500 inclusively. ";

return guess;

}

/* The function checkList checks the number input by the caller to the list.

The function returns either a True (when the guess is correct) or a False

(when the guess is not in the list).

*/

int binarySearch(int anyArray[],int first, int last, int guess) {

// declare variables

/* a Boolean variable named found initialized to false to control the loop */

int index;

if (first > last)

index = -1;

else {

int mid = (first + last)/2;

if (guess == anyArray[mid])

index = mid;

else

if (guess < anyArray[mid])

index = binarySearch(anyArray, first, mid-1, guess);

else

index = binarySearch(anyArray, mid+1, last, guess);

} // end if

return index;

}

/* The function displayPrize displays the prize won. */

void displayPrize(int numberGuesses, int location, int guess) {

cout << " Caller. Your number " << guess

<< " was found at location " << location

<< " of the list Counting you, there were "

<< numberGuesses << " callers. "

<< "Your winnings are $10,000. ";

}

void sortList(int anyArray[], int len) {

// ****** your code for sorting the array goes here *****

}

void printList(int anyArray[], int len) {

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

cout << anyArray[i] << "\t";

cout << endl;

}