Need help. Lab 10 – Searching and Sorting Objectives: · Use a single dimension a
ID: 3858085 • Letter: N
Question
Need help.
Lab 10 – Searching and Sorting
Objectives:
· Use a single dimension array
· Use a menu to call various functions
· Use multiple sorts and searches
Instructions:
Code a program with functions to sequentialSearch, binarySearch and sort an array with 2 different algorithms, along with a getSize function, print menu function, a printTheArray function, fillWithRandom function and a dispatch function. Also set up a 100 position integer array and an integer variable, called size, globally (before all methods are coded). Then the array and size do not have to be passed to any of these functions. (The alternative approach would be to define the array in the dispatch method after reading in a size. Then array name and size would be passed to all methods.) The menu should look like the following:
0. Exit
1. Get the size needed for today’s use of the array.
2. Fill an array with random numbers from 1-100.
3. Print the array with position numbers.
4. Sort the array in ascending sequence
5. Sort the array in descending sequence – use a different sort algorithm from step 4.
6. Sequential search of the array for a target – target should be passed to method and the method returns the found location or -1.
7. Binary search of the array for a target – target should be passed to method and the method returns the found location or -1. Remember that the array must be sorted before calling the binary search function.
Run:
The program should start with a request for a size from the user. (Type in 15.) Run the lab in this order:
Ask the user for the size of the array (1)
Fill the array with random values (2)
Print the array (3) (List the position number and the contents of the array position)
Sequentially search the array for a number in the array and then one not in the array, printing the appropriate messages of “Found in position ____” and “Not Found” (6, 6)
Sort the array into ascending sequence (4)
Print the array (3)
Do a binary search of the array for a number in the array and then for a value not in the array, printing the appropriate messages of “Found in position ____” and “Not Found” (7, 7)
Sort the array into descending sequence (5) (Use a different sort algorithm from code 4)
Finally, print the array again (3)
The main method will look like this: (everything else will be done in other functions)
int main ()
{
printMenu();
cout << “Type in a choice “ << endl;
cin >> choice;
while (choice != 0)
{
dispatch (choice); // one big switch statement
printMenu();
cout << “Type in a choice “ << endl;
cin >> choice;
}
return 0;
}
For the two search methods (choice 6 and 7), the program must ask for the target and then read in a target before calling the search method. After calling the search method, the program must determine if the search returned an integer (print “Found in position ______”) or the search returned a -1 (print “Not Found”).
Explanation / Answer
#include<iostream>
using namespace std;
int size;
int a[100];
int sequentialSearch(int n)
{
for(int i=0;i<100;i++)
{
if(n==a[i])
{
return (i+1);
}
}
return -1;
}
int binarySearch(int n)
{
int low=0,high=100,mid;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid]==n)
{
return mid+1;
}
else if(a[mid]>n)
high=mid-1;
else if(a[mid]<n)
low=mid-1;
}
return -1;
}
void sort1()
{
int i, j;
for (i = 0; i < 100-1; i++)
{
for (j = 0; j < 100-i-1; j++)
if (a[j] > a[j+1])
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
void sort2()
{
int i, j, m;
for (i = 0; i < 100-1; i++)
{
m = i;
for (j = i+1; j < 100; j++)
{
if (a[j] > a[m])
m = j;
}
int temp=a[m];
a[m]=a[i];
a[i]=temp;
}
}
int getSize()
{
return sizeof(a[0])/sizeof(a);
}
void printMenu()
{
cout<<" 0. Exit ";
cout<<"1.Get the size needed for today’s use of the array. ";
cout<<"2.Fill an array with random numbers from 1-100. ";
cout<<"3.Print the array with position numbers. ";
cout<<"4.Sort the array in ascending sequence ";
cout<<"5.Sort the array in descending sequence ";
cout<<"6.Sequential search of the array for a target – target should be passed to method and the method returns the found location or -1. ";
cout<<"7.Binary search of the array for a target – target should be passed to method and the method returns the found location or -1. Remember that the array must be sorted before calling the binary search function. ";
}
void printTheArray()
{
for(int i=0;i<100;i++)
{
cout<<a[i]<<" is at position :"<<i+1<<endl;
}
}
void fillWithRandom()
{
for(int i=0;i<100;i++)
{
int x=rand()%101;
a[i]=x;
}
}
void dispatch(int ch)
{
switch(ch)
{
case 1:cout<<"Size of array :"<<getSize();
break;
case 2:fillWithRandom();
break;
case 3: printTheArray();
break;
case 4:sort1();
break;
case 5:sort2();
break;
case 6:
{
cout<<"Enter he no.you want to search ";
int t;
cin>>t;
int res1=sequentialSearch(t);
if(res1!=-1)
cout<<"Found in position :"<<res1<<endl;
else if(res1==-1)
cout<<"Not Found ";
break;
}
case 7:
{
cout<<"Enter the no.you want to search ";
int t;
cin>>t;
int res=binarySearch(t);
if(res!=-1)
cout<<"Found in position :"<<res<<endl;
else if(res==-1)
cout<<"Not Found ";
break;
}
default:cout<<"wrong choice ";
}
}
int main ()
{
printMenu();
int choice;
cout<<"Type in a choice"<<endl;
cin>>choice;
while(choice!=0)
{
dispatch(choice); // one big switch statement
printMenu();
cout<<"Type in a choice"<<endl;
cin>>choice;
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.