My program isn\'t performing the first option properly, it\'s only allowing the
ID: 3682803 • Letter: M
Question
My program isn't performing the first option properly, it's only allowing the user to enter one number. i have the guidelines first and then my program below it.
Design, write, execute, and test a C++ program that will demonstrate the use of several sort and search routines by allowing the user to work with an ongoing, "current" list by repeatedly choosing actions from the following menu:
1. Reset the current list from the keyboard 2. Reset the current list using randomly generated elements 3. Perform Bubble Sort on the current list 4. Perform Insertion Sort on the current list 5. Perform Selection Sort on the current list 6. Perform Linear Search on the current list 7. Perform Binary Search on the current list 8. Quit the program
Here are some requirements for your program:
Your program should be able to handle lists with up to 50 items.
When your program starts executing, it should automatically start with a current list of 0 items; in other words, the current list should start off as an empty list. Your program should track the fact that this empty current list is known to be ordered.
Before displaying the menu each time, the program should display the current list. If the current list is empty, then the phrase "(empty)" should be displayed. The current order status (known or not known to be ordered) should also be displayed.
Whenever the user chooses to reset the current list from the keyboard, the user should then be allowed to enter in between 0 and 50 positive elements from the keyboard, signaling the end of the input by entering the "sentinel" element of -1.
Whenever the user chooses to reset the current list using randomly generated elements, the user should be asked for the size of the list (a value between 0 and 50), as well as the lowest lower and upper limits that the elements in the list could have (the "range" of the elements), and then the program should automatically generate list elements within the given range using the random number generator.
#include <iostream>
using namespace std;
const int MLS = 50;
typedef int element;
const element SENTINEL = -1
element read_element ();
class Alist {
private:
element items[MLS];
int size;
void swap();
public:
void Read();
void Print();
void BubbleSort();
void InsertionSort();
void SelectionSort();
void LinearSearch();
void BinarySearch();
} ;
int main() {
Alist B;
B.Read();
B.Print();
B.BubbleSort();
B.Print();
char action;
cout << "Sort and Search Program!" << endl;
cout << "Current list: "
cout << "Actions: " << endl;
cout << "1. Reset the current list from the keyboard" << endl;
cout << "2. Reset the current list using randomly generated
elements" << endl;
cout << "3. Perform Bubble Sort on the current list." << endl;
cout << "4. Perform Insertion Sort on the current list." << endl;
cout << "5. Perform Selection Sort on the current list." << endl;
cout << "6. Perform Linear Search on the current list." << endl;
cout << "7. Perform Binary Search on the current list." << endl;
cout << "8. Quit the program." << endl;
cout << "Choose an action: " ;
cin >> action;
switch(action){//Allows user to choose what menu action to perform.
case'1':
cout << "Resetting the current list from the
keyboard." << endl;
B.Read();
B.Print();
}
void Alist::Print(){
//PRE: The N.O. Alist is valid.
//POST: The N.O. Alist has had items elements displayed to the user.
for(int i=0; i < size; i++)
cout << items[i] << endl;
}
void Alist::Read() {
//PRE: none
//POST: The N.O. Alist is valid, using data from user.
element userval;
size = 0;
cout << "Enter elements," << SENTINEL << " to stop: ";
userval = read_element ();
while(userval != SENTINEL) && (size < MLS) {
items [size] = userval;
size++;
if (size < MLS)
userval = read_element();
else
cout << "List is now full." << endl;
}
void Alist::BubbleSort () {
//PRE: The N.O. Alist is valid.
//POST: The N.O. Alist is unchanged, except its elements have been
//put into ascending order.
for (int i=0; i< size-1; i++)
for (int j=0; j< size-1-i; j++)
if (items[j] > items[j+1])
swap (j,j+1);
else
;
void Alist::Swap (int pos1, int pos2) {
//PRE: The N.O. Alist is valid.
//POST: Must be >= 0 and size of pos2
//Must be >=0 and < size
element temp;
temp = items[pos1];
items[pos1] = items[pos2];
items[pos2] = temp;
}
void Alist::InsertionSort () {
//PRE: The N.O. is valid.
//POST: The N.O. Alist is unchanged, except its elements have been put
//in ascending order.
bool done;
int j;
for (int i-1; i < size; i++) {
done = false;
j = i;
while((!done)&&(j>=1))
if(items[j] < items[j-1]) {
swap (j, j-1);
j--;
else
done = true;
}
}
void Alist::SelectionSort() {
//PRE: The N.O. is valid.
//POST: The N.O. Alist is unchanged, except its elements have been put
//in ascending order.
int maxpos;
for (int i=size-1; i>0; i--)
maxpos=0;
for (int j=; j<=i; j++)
if (items[j] > items[maxpos])
maxpos = j;
else
;
swap(maxpos, i);
}
void Alist::LinearSearch (element target, bool & found, int & position){
//PRE: The N.O. Alist is valid and target is a valid element.
//POST: If target exist on N.O. Alist, then found will be set to
//true and position will be set to a location of the target of the
//target on the N.O. Alist. Otherwise, found will be set to false
//and position will be undefined.
found = false;
position = 0;
while ((!found) && (position < size))
if (target == items[position])
found = true;
else
position++;
}
void Alist::BinarySearch (element target, bool & found, int & position) {
//PRE: The N.O. Alist is valid and target is a valid element.
//POST: If target exists on N.O. Alist, then found will be set to
//true and position will be set to a location of the target on the
//N.O. Alist. Otherwise, found will be set to false and position
//will be undefined.
int low;
int high;
int mid;
found = false;
low = 0;
high = size-1
while ((!found) && (low <= high))
mid = (low + high)/2;
if (target == items[mid]) {
found = true;
position = mid;
}
else if (target < items[mid])
high = mid-1;
else
low = mid+1;
}
void rand_list()
{
int size;
cout
cin>>size;
int random;
int arr[size];
int index=0;
int l_cap,u_cap;
cout<<"enter the range";
cin>>l_cap>>u_cap;
while(index<size)
{
random = rand() % 10 + 1;
if(random>l_cap && random < u_cap)
{
arr[index]= random;
index++;
}
}
}
Explanation / Answer
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
//global section:
const int MLS = 50; //size of array
typedef int element; //datatype of "element"
const element SENTINEL = -1; //"element value" that ends user input
//global function prototypes:
element read_element();
int read_int();
void display_menu();
//array list class prototype:
class AList {
private:
element items[MLS];
int size;
bool list_ordered;
//-I/O:
void Print();
void Read();
void GenRandList(int list_size, int range_high, int range_low);
void Swap(element first, element second);
//-Sorts:
void BubbleSort(int & comps, int & moves);
void InsertionSort(int & comps, int & moves);
void SelectionSort(int & comps, int & moves);
//-Searches:
void LinearSearch(element target, bool & found, int & position,
int & comps);
void BinarySearch(element target, bool & found, int & position,
int & comps);
//-Stats:
int CalcQuad();
int CalcLog();
public:
void FirstLoad();
void Run_Print();
void Run_Read();
void Run_GenRandList();
void Run_BubbleSort();
void Run_InsertionSort();
void Run_SelectionSort();
void Run_LinearSearch();
void Run_BinarySearch();
};
//****main function****
int main() {
srand(int(time(0))); //seed the random number generator
AList myAList; //create object
myAList.FirstLoad(); //prepares object for use
int menu_option; //input - user menu choice
//loop menu
do {
myAList.Run_Print();
display_menu();
menu_option = read_int();
switch (menu_option) {
case 1:
myAList.Run_Read();
break;
case 2:
myAList.Run_GenRandList();
break;
case 3:
myAList.Run_BubbleSort();
break;
case 4:
myAList.Run_InsertionSort();
break;
case 5:
myAList.Run_SelectionSort();
break;
case 6:
myAList.Run_LinearSearch();
break;
case 7:
myAList.Run_BinarySearch();
break;
case 8:
cout << endl << "Quitting Sort and Search "
<< "Demo Program, version 1.0" << endl;
break;
default:
cout << endl << "Invalid choice; Please choose"
<< "between menu options 1-8" << endl
<< endl;
break;
}
} while (menu_option != 8);
}
//type checks input to see if it matches "element"
//if element is int, will also make certain
//range is between -2147483648 and 2147483648
element read_element() {
//variable dec+def
element user_input; //input - user input
//type checking
cin >> user_input;
while (!cin.good()){
cout << "Bad input datatype; Try again: ";
cin.clear();
cin.ignore(80, ' ');
cin >> user_input;
}
return user_input;
}
//type checks input to ensure it is an integer
int read_int() {
//variable dec+def
int user_input; //input - user input
//type checking
cin >> user_input;
while (!cin.good()){
cout << "Response must be a whole number, try again: ";
cin.clear();
cin.ignore(80, ' ');
cin >> user_input;
}
return user_input;
}
//displays the main menu to the user
void display_menu() {
cout << "Actions:" << endl
<< " 1. Reset the current list from the keyboard" << endl
<< " 2. Reset the current list using "
<< "randomly generated elements" << endl
<< " 3. Perform Bubble Sort on the current list" << endl
<< " 4. Perform Insertion Sort on the current list" << endl
<< " 5. Perform Selection Sort on the current list" << endl
<< " 6. Perform Linear Search on the current list" << endl
<< " 7. Perform Binary Search on the current list" << endl
<< " 8. Quit the program" << endl << endl
<< "Choose an action: ";
}
//prints the entire contents of the list
void AList::Print() {
//Pre: the Native Object AList is valid
//Post: the Native Object AList is unchanged, and its elements are
//displayed
for (int i = 0; i < size; i++)
cout << items[i] << " ";
}
//fills the list with a series of user element inputs
void AList::Read() {
//Pre: none
//Post: the Native Object AList is valid
element userval; //input - user input of a single element
size = 0; //LCV - size of array, items[]
//Read data from user
cout << "Enter a series of elements, " << SENTINEL
<< " to stop: ";
userval = read_element();
while ((size < MLS) && (userval != SENTINEL)) {
items[size] = userval;
size++;
if (size >= MLS)
cout << "The array is full, exiting." << endl;
else
userval = read_element();
}
//List is not known to be ordered after input
list_ordered = false;
}
//fills the list with a series of randomly generated elements
void AList::GenRandList(int list_size, int range_high, int range_low) {
//Pre: none
//Post: the Native Object AList is valid
size = 0; //LCV - size of array, items[]
//create list with randomly generated values
while (size < list_size) {
items[size] = (rand() % (range_high - range_low + 1))
+ range_low;
size++;
}
//List is not known to be ordered after input
list_ordered = false;
}
//swaps the elements in the position specified
void AList::Swap(element first, element second) {
//Pre: the Native Object AList is valid
//Post: the Native Object Alist is unchanged, except elements
//in position [first] and [second] has swapped places
element temp;
temp = items[first];
items[first] = items[second];
items[second] = temp;
}
//sorts the list using bubble sort
void AList::BubbleSort(int & comps, int & moves) {
//Pre: the Native Object AList is valid
//Post: the Native Object AList is unchanged, except its elements
//are in ascending order
comps = 0; //Accumulator - counts # comparisons
moves = 0; //Accumulator - counts # moves
for (int i = 0; i < size - 1; i++)
for (int j = 0; j < size - 1 - i; j++) {
comps++;
if (items[j] > items[j+1]) {
moves += 3;
Swap(j, j+1);
}
else
;
}
//List is known to be ordered after sorting
list_ordered = true;
}
//sorts the list using insertion sort
void AList::InsertionSort(int & comps, int & moves) {
//Pre: the Native Object AList is valid
//Post: the Native Object AList is unchanged, except its elements
//are in ascending order
int j; //LCV - keeps track of current element position
bool done; //LCV - when elements to its left are sorted, true
comps = 0; //Accumulator - counts # comparisons
moves = 0; //Accumulator - counts # moves
for (int i = 1; i < size; i++) {
j = i;
done = false;
while ( (j >= 1) && (!done) ) {
comps++;
if (items[j] < items[j-1]) {
moves += 3;
Swap (j, j-1);
j--;
}
else
done = true;
}
}
//List is known to be ordered after sorting
list_ordered = true;
}
//sorts the list using selection sort
void AList::SelectionSort(int & comps, int & moves) {
//Pre: the Native Object AList is valid
//Post: the Native Object AList is unchanged, except its elements
//are in ascending order
int maxpos; //LCV - location of highest value
comps = 0; //Accumulator - counts # comparisons
moves = 0; //Accumulator - counts # moves
for (int i = size - 1; i > 0; i--) {
maxpos = 0;
for (int j = 1; j <= i; j++) {
comps++;
if (items[j] > items[maxpos])
maxpos = j;
else
;
}
moves += 3;
Swap(maxpos, i);
}
//List is known to be ordered after sorting
list_ordered = true;
}
//searches the list for the specified target, using linear search
void AList::LinearSearch(element target, bool & found, int & position,
int & comps) {
//Pre: the Native Object AList is valid and target is a valid element
//Post: 1) if target exist on the Native Object Alist,
//found will be true and position will be a location of the
//target on N.O. AList
// 2) otherwise, target will be false and position will be
// undefined (make no promises)
found = false; //LCV - target not found at first
position = 0; //LCV - position of current position
comps = 0; //Accumulator - counts # comparisons
while ( (!found) && (position < size) ) {
comps++;
if (items[position] == target)
found = true;
else
position++;
}
}
//searches the list for the specified target, using binary search
void AList::BinarySearch(element target, bool & found, int & position,
int & comps) {
//Pre: the Native Object Alist is valid AND in ascending order and
//target is a valid element
//Post: 1) if target exist on the Native Object Alist,
//found will be true and position will be a location of the
//target on N.O. AList
// 2) otherwise, target will be false and position will be
// undefined (make no promises)
int low; //LCV - lowest position of "interesting" part of list
int high; //LCV - highest position of "interesting" part of list
int mid; //LCV - middle position of "interesting" part of list
found = false; //LCV - target not found at first
comps = 0; //Accumulator - counts # comparisons
low = 0;
high = size - 1;
while ( (!found) && (low <= high) ) {
mid = (low + high) / 2;
comps++;
if (target == items[mid]) {
found = true;
position = mid;
}
else if (target < items[mid]) {
comps++;
high = mid - 1;
}
else {//target > items[mid]
comps++;
low = mid + 1;
}
}
}
//calculates the theoretical computations/moves required for quadratic sorts
int AList::CalcQuad() {
int result; //result of theoretical quadratic comp/move
result = (size * size / 2) - (size / 2);
return result;
}
//calculates the theoretical computations required for logarithmic searches
int AList::CalcLog() {
int remain; //LCV - size of list; size of list as it's halved
int counter; //Accumulator - counts # times list is halved
remain = size;
counter = 0;
while (remain > 0) {
remain /= 2;
counter++;
}
return counter;
}
//should be called right after the creation of the object
//sets the N.O. AList to be a valid empty list
void AList::FirstLoad() {
//Pre: the N.O. AList cannot be valid
//Post: the N.O. AList is valid (specifically, AList is empty)
size = 0;
list_ordered = true;
}
//runs Print()
void AList::Run_Print() {
cout << "Current list: ";
//display contents of list
if (size > 0)
Print();
else //size <= 0
cout << "(empty) ";
if (list_ordered == true)
cout << "(KNOWN to be ordered)" << endl << endl;
else //list_ordered == false
cout << "(NOT KNOWN to be ordered)" << endl << endl;
}
//runs Read(), display output
void AList::Run_Read() {
cout << endl << "Resetting the current list from the keyboard."
<< endl << endl;
Read();
cout << endl << "Finished resetting, " << size
<< " elements entered." << endl << endl;
}
//runs GenRandList(), display output
void AList::Run_GenRandList() {
int list_size; //input - desired list size
int range_high; //input - desired upper limit
int range_low; //input - desired lower limit
cout << endl << "Resetting the current list "
<< "using randomly generated elements." << endl << endl;
//get desired list size
cout << "Enter the desired number of elements (0 to " << MLS << "): ";
list_size = read_int();
while ((list_size > MLS) || (list_size < 0)) {
cout << "Response must be between 0 and " << MLS
<< ", try again: ";
list_size = read_int();
}
//get desired lower limit
cout << "Enter the lower limit of the range: ";
range_low = read_int();
//get desired upper limit
cout << "Enter the upper limit of the range: ";
range_high = read_int();
while (range_high < range_low) {
cout << "Must be a value higher than " << range_low
<< ", try again: ";
range_high = read_int();
}
GenRandList(list_size, range_high, range_low);
//display confirmation
cout << endl << "Finished resetting, " << size
<< " elements between " << range_low
<< " and " << range_high
<< " randomly generated." << endl << endl;
}
//runs BubbleSort(), display calculations/moves required for sort
void AList::Run_BubbleSort() {
int comps; //Accumulator - counts # comparisons
int moves; //Accumulator - counts # moves
cout << endl << "Performing Bubble Sort on the current list." << endl;
BubbleSort(comps, moves);
cout << endl << "Theoretical sort statistics: " << CalcQuad()
<< " element comparisons, " << 3 * CalcQuad()
<< " element movements " << endl;
cout << "Actual sort statistics: " << comps
<< " element comparisons, " << moves
<< " element movements " << endl;
cout << endl << "Finishing Bubble Sort." << endl << endl;
}
//runs InsertionSort(), display calculations/moves required for sort
void AList::Run_InsertionSort() {
int comps; //Accumulator - counts # comparisons
int moves; //Accumulator - counts # moves
cout << endl << "Performing Insertion Sort on the current list."
<< endl;
InsertionSort(comps, moves);
cout << endl << "Theoretical sort statistics: " << CalcQuad()
<< " element comparisons, " << 3 * CalcQuad()
<< " element movements " << endl;
cout << "Actual sort statistics: " << comps
<< " element comparisons, " << moves
<< " element movements " << endl;
cout << endl << "Finishing Insertion Sort." << endl << endl;
}
//runs SelectionSort(), display calculations/moves required for sort
void AList::Run_SelectionSort() {
int comps; //Accumulator - counts # comparisons
int moves; //Accumulator - counts # moves
cout << endl << "Performing Selection Sort on the current list."
<< endl;
SelectionSort(comps, moves);
cout << endl << "Theoretical sort statistics: " << CalcQuad()
<< " element comparisons, ";
if (size > 0)
cout << 3 * (size - 1);
else
cout << 0;
cout << " element movements " << endl;
cout << "Actual sort statistics: " << comps
<< " element comparisons, " << moves
<< " element movements " << endl;
cout << endl << "Finishing Selection Sort." << endl << endl;
}
//runs LinearSearch(), display output, and calculations required for search
void AList::Run_LinearSearch() {
element target; //input - element user wants to find
bool found; //LCV - target not found at first
int position; //LCV - position of current position
int comps; //Accumulator - counts # comparisons
cout << endl << "Performing Linear Search on the current list."
<< endl << endl;
//get desired target from user
cout << "Enter a target element to search for: ";
target = read_element();
LinearSearch(target, found, position, comps);
if (found == true)
cout << endl << "The target was FOUND on the current list "
<< "in position " << position << "." << endl;
else // found == false
cout << endl << "The target was NOT FOUND on the current list."
<< endl;
cout << endl << "Theoretical search statistics: " << size
<< " element comparisons" << endl;
cout << "Actual search statistics: " << comps
<< " element comparisons" << endl;
cout << endl << "Finishing Linear Search." << endl << endl;
}
//runs BinarySearch(), display output, and calculations required for search
void AList::Run_BinarySearch() {
//only run binary search when the list is known to be ordered
if (list_ordered == true) {
element target; //input - element user wants to find
bool found; //LCV - target not found at first
int position; //LCV - position of current position
int comps; //Accumulator - counts # comparisons
cout << endl << "Performing Binary Search on the current list."
<< endl << endl;
//get desired target from user
cout << "Enter a target element to search for: ";
target = read_element();
BinarySearch(target, found, position, comps);
if (found == true)
cout << endl << "The target was FOUND on "
<< "the current list in position "
<< position << "." << endl;
else // found == false
cout << endl << "The target was NOT FOUND "
<< "on the current list." << endl;
cout << endl << "Theoretical search statistics: "
<< 2 * CalcLog() << " element comparisons" << endl;
cout << "Actual search statistics: " << comps
<< " element comparisons" << endl;
cout << endl << "Finishing Binary Search." << endl << endl;
}
else //list_ordered == false
cout << endl << "Sorry, since the current list is not known "
<< "to be ordered, the Binary Search" << endl
<< "cannot be performed at this time. "
<< "Please sort the current list first."
<< endl << endl;
}
sample output
Current list: (empty) (KNOWN to be ordered)
Actions:
1. Reset the current list from the keyboard
2. Reset the current list using randomly generated elements
3. Perform Bubble Sort on the current list
4. Perform Insertion Sort on the current list
5. Perform Selection Sort on the current list
6. Perform Linear Search on the current list
7. Perform Binary Search on the current list
8. Quit the program
Choose an action: 1
Resetting the current list from the keyboard.
Enter a series of elements, -1 to stop: 10 4 3 8 4 5 9 -1
Finished resetting, 7 elements entered.
Current list: 10 4 3 8 4 5 9 (NOT KNOWN to be ordered)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.