Programming Language: C++ Lab 10 – Searching and Sorting Objectives: Use a singl

Q: Programming Language: C++ Lab 10 – Searching and Sorting Objectives: Use a singl

// C++ code #include #include using namespace std; int arr[100],n,i,j; int ch,pos; void printMenu() { cout

ID: 3818738 • Letter: P

Question

Programming Language: C++

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 search and sort an array, along with a print menu 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.)

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”).

Submission: Turn in your source and output file to D2L in a zipped folder.

Explanation / Answer

// C++ code
#include <iostream>
#include <stdlib.h>
using namespace std;

int arr[100],n,i,j;
int ch,pos;

void printMenu()
{
cout<<" 0.Exit 1.Initialise the array ";

cout<<"2.Print the array with position numbers. ";
cout<<"3.Sort the array in ascending sequence ";
cout<<"4.Sort the array in descending sequence ";
cout<<"5.Sequential search of the array for a target ";
cout<<"6.Binary search of the array for a target ";

}
void initArray()
{
cout<<"enter the size of the array: ";
cin>>n;
cout<<" enter random numbers from 1-100 "<<endl;
for(i=0;i<n;i++)
{
cin>>arr[i];
}
}

void prntArray()
{
cout<<"Array elements with positions are:"<<endl;
for(i=0;i<n;i++)
{
cout<<i<<"->"<<arr[i]<<" ";
}
}

void sortAsc() //ascending order sorting
{
//using bubble sorting technique

for (i = 0; i < n; ++i)
for (j = 0; j < n - i - 1; ++j)
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}

void sortDesc()///descending order sorting
{
//using selection sort
int max;
for (int i = 0; i < n-1; ++i)
{
max = i;
for (int j = i + 1; j < n; ++j)
{

if (arr[j] > arr[max])
{
max = j;

}

// swap arr[i], arr[max]
int temp = arr[i];
arr[i] = arr[max];
arr[max] = temp;

}
}

int seqSrch() //sequential search
{
int target;
cout<<"enter the target value: ";
cin>>target;

for(i=0;i<n;i++)
{
if(arr[i] == target)
{
return i;
}

}
return -1;
}
int binSrch() //binary search
{
int target,first,last,middle;
sortAsc(); //to sort the array in ascending order
cout<<"Sorting is done for binary search ";
prntArray();
cout<<" enter the target value: ";
cin>>target;

first = 0;
last = n-1;
middle = (first+last)/2;
while (first <= last)
{
if(arr[middle] < target)
{
first = middle + 1;

}
else if(arr[middle] == target)
{
return middle;

}
else
{
last = middle - 1;
}
middle = (first + last)/2;
}

if(first > last)
{
return -1;
}

}

void dispatch(int ch)
{
switch(ch)
{
case 0: exit(0);
break;
case 1: initArray();
break;
case 2: prntArray();
break;
case 3: sortAsc();
break;
case 4: sortDesc();
break;
case 5: pos = seqSrch();
if(pos==-1)
{ cout<<"Not found!";

}
else
cout<<"Item found at position "<<pos;
break;
case 6: pos = binSrch();
if(pos==-1)
{ cout<<"Not found!";

}
else
cout<<"Item found at position "<<pos;
break;
}

}
int main()
{
printMenu();

cout<<" enter choice: ";
cin>>ch;
while(ch!=0)
{
dispatch(ch);
printMenu();

cout<<" enter choice: ";
cin>>ch;
}
return 0;
}

/*
output:

0.Exit
1.Initialise the array
2.Print the array with position numbers.
3.Sort the array in ascending sequence
4.Sort the array in descending sequence
5.Sequential search of the array for a target
6.Binary search of the array for a target

enter choice: 1
enter the size of the array: 5

enter random numbers from 1-100
34
33
23
11
10

enter choice: 2
Array elements with positions are:
0->34 1->33 2->23 3->11 4->10

enter choice: 3

enter choice: 2
Array elements with positions are:
0->10 1->11 2->23 3->33 4->34

enter choice: 4

enter choice: 2
Array elements with positions are:
0->34 1->33 2->23 3->11 4->10

enter choice: 5
enter the target value: 23
Item found at position 2

enter choice: 6
Sorting is done for binary search
Array elements with positions are:
0->10 1->11 2->23 3->33 4->34
enter the target value: 23
Item found at position 2

enter choice: 0

Navigate

Programming Language: C++ For this project, you will practice decomposing a prob

Programming Language: JAVA Driver.java /** * * Number System Converters * */ imp

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Programming Language: C++ Lab 10 – Searching and Sorting Objectives: Use a singl

Question

Explanation / Answer

Related Questions

Navigate