im having trouble completing this program. Here is the guidelines for the progra
ID: 3681999 • Letter: I
Question
im having trouble completing this program.
Here is the guidelines for the program and beneath that is what i have written for my program so far.
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;
}
Explanation / Answer
Hi, I have implemented all necessary functionality and corrected many errors.
Please test and give me feedback.
#include<iostream>
#include<stdlib.h>
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(int,int);
public:
Alist();
void Read();
void ReadRandom();
void Print();
void BubbleSort();
void InsertionSort();
void SelectionSort();
void LinearSearch (element target, bool & found, int & position);
void BinarySearch (element target, bool & found, int & position);
};
int main(){
Alist B;
char action;
cout << "Sort and Search Program!" << endl;
cout << "Current list: ";
do{
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. Display List." << endl;
cout << "9. Quit the program." << endl;
cout << "Choose an action: " ;
cin >> action;
int position;
int target;
bool found;
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();
break;
case'2':
cout << "Resetting the current list from random number in range 1-100." << endl;
B.ReadRandom();
B.Print();
break;
case'3':
cout << "Performing bubble sort." << endl;
B.BubbleSort();
B.Print();
break;
case'4':
cout << "Performing Insertion sort." << endl;
B.InsertionSort();
B.Print();
break;
case'5':
cout << "Performing Selection Sort." << endl;
B.SelectionSort();
B.Print();
break;
case'6':
cout << "Performing Linear search" << endl;
found = false;
position = -1;
cout<<"Enter target element: ";
target = read_element();
B.LinearSearch (target,found,position);
if(found){
cout<<"Target element found at index "<<position<<endl;
}
else
cout<<"Element not found"<<endl;
break;
case '7':
cout << "Performing Binary search" << endl;
found = false;
position = -1;
cout<<"Enter target element: ";
target = read_element();
B.BinarySearch ( target, found, position);
if(found){
cout<<"Target element found at index "<<position<<endl;
}
else
cout<<"Element not found"<<endl;
break;
case '8':
cout<<"Displaying list:"<<endl;
B.Print();
break;
case '9':
break;
default:
cout<<"Wrong option"<<endl;
}
}while(action!='9');
return 0;
}
Alist::Alist(){
size = 0;
}
void Alist::Print(){
for(int i=0; i < size; i++)
cout << items[i] << " ";
cout<<endl;
}
void Alist::Read() {
cout << "Enter elements," << SENTINEL << " to stop: ";
int 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::ReadRandom() {
while((size < MLS)) {
items [size] = rand()%100 +1;// filling with random number in range 1-100
size++;
}
cout<<"Array has filled with random numbers in range 1-100"<<endl;
}
void Alist::BubbleSort() {
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);
}
}
void Alist::Swap(int pos1, int pos2) {
element temp;
temp = items[pos1];
items[pos1] = items[pos2];
items[pos2] = temp;
}
int read_element() {
int t;
cin>>t;
return t;
}
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>=0)){
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=i;
for (int j=0; j<=i; j++)
if (items[j] > items[maxpos])
maxpos = j;
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;
}
}
/*
Sample run:
Sort and Search Program!
Current list: 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. Display List.
9. Quit the program.
Choose an action: 2
Resetting the current list from random number in range 1-100.
Array has filled with random numbers in range 1-100
84 87 78 16 94 36 87 93 50 22 63 28 91 60 64 27 41 27 73 37 12 69 68 30 83 31 63 24 68 36 30 3 23 59 70 68 94 57 12 43 30 74 22 20 85 38 99 25 16 71
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. Display List.
9. Quit the program.
Choose an action: 3
Performing bubble sort.
3 12 12 16 16 20 22 22 23 24 25 27 27 28 30 30 30 31 36 36 37 38 41 43 50 57 59 60 63 63 64 68 68 68 69 70 71 73 74 78 83 84 85 87 87 91 93 94 94 99
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. Display List.
9. Quit the program.
Choose an action: 8
Displaying list:
3 12 12 16 16 20 22 22 23 24 25 27 27 28 30 30 30 31 36 36 37 38 41 43 50 57 59 60 63 63 64 68 68 68 69 70 71 73 74 78 83 84 85 87 87 91 93 94 94 99
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. Display List.
9. Quit the program.
Choose an action: 6
Performing Linear search
Enter target element: 25
Target element found at index 10
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. Display List.
9. Quit the program.
Choose an action: 9
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.