CREATE DETAILED PSEUDOCODE FOR THE FOLLOWING SOURCE CODE: #include <algorithm> #
ID: 3846564 • Letter: C
Question
CREATE DETAILED PSEUDOCODE FOR THE FOLLOWING SOURCE CODE:
#include <algorithm>
#include <iostream>
#include <climits>
#include<cstdlib>
#include <ctime>
#include <vector>
using namespace std;
void displayVector(vector<int> vect)
{
std::cout<<" Vector: ";
for(int i = 0; i < vect.size(); i++)
{
std::cout << vect[i] << " ";
}
}
void mergeVA(vector<int> &vect, int size, int l, int middle, int h)
{
int i, j, k;
int n1 = middle - l + 1;
int n2 = h - middle;
int leftSide[n1], rightSide[n2];
for (i = 0; i < n1; i++)
leftSide[i] = vect[l + i];
for (j = 0; j < n2; j++)
rightSide[j] = vect[middle + 1+ j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (leftSide[i] <= rightSide[j])
{
vect[k] = leftSide[i];
i++;
}
else
{
vect[k] = rightSide[j];
j++;
}
k++;
}
while (i < n1)
{
vect[k] = leftSide[i];
i++;
k++;
}
while (j < n2)
{
vect[k] = rightSide[j];
j++;
k++;
}
}
void sort(vector<int> &vect, int size, int l, int h)
{
if (l < h){
int middle = (l + h) / 2;
sort(vect, size, l, middle);
sort(vect, size, middle+1, h);
mergeVA(vect, size, l, middle, h);
}
}
unsigned search(vector<int> vect, int val)
{
size_t mid, left = 0 ;
size_t right = vect.size();
while (left < right)
{
mid = left + (right - left)/2;
if (val > vect[mid]){
left = mid+1;
}
else if (val < vect[mid]){
right = mid;
}
else {
if(val== vect[mid])
return mid;
}
}
return UINT_MAX;
}
int main()
{
vector<int> vect;
int value,n,RandMax;
cout<<"Enter maximum value: ";
cin>>RandMax;
cout<<"Enter the number 50 to create vector: ";
cin>>n;
for(int i=0;i<n;i++)
{
value=rand() % RandMax + 1;
vect.push_back(value);
}
displayVector(vect);
cout << endl;
sort(vect,vect.size(),0, vect.size());
cout<<"Sorted Vector: ";
displayVector(vect);
cout << endl;
cout << "Enter a number to search for: ";
cin >> value;
unsigned pos = search(vect, value);
if (pos != UINT_MAX)
{
cout << endl<<value<<" has been found at index: "<< pos << endl;
}
else
{
cout << endl <<value<<" Invalid Entry!" << endl;
}
cout << endl;
return 0;
}
Explanation / Answer
//This program starts from main
//takes maximum value to insert random values into array with that range
//after inserting random values into array, the program will passes the array into sort function
//sort function will sort the array by using merge sort algorithm by using concept called divide and conquere
//after sorting the array, it will search for an element
//for searching the program uses binary search algorithm
//if entered element found in the array, then it will display the position where it is found
//else not
//Sort
sort():
if (left half < right half):
1.find middle point to divide into 2 halves
2.send left half to sort to divide into further
3.send right half to sort to divide into further
4.mergeVA()<-- calling mergeVA() function to merge the divided elements as sorted
//Merge
mergeVA():
Merge 2 sub arrays
Left sub array is from 1 to middle
Right sub array is from middle+1 to last
while:
if Left sub array is less than Right sub array:
move Left sub array element into newArray
else
move Right sub array element into new Array
copy the remaining elements of Left sub array if there are any
copy the remaining elements of Right sub array if there are any
//Search
search(value):
while:
mid<-- left+(right-left)/2
if value > vect[mid]
left=mid+1
else if
right=mid
else
if value==vect[mid]
return mid
return UINT_MAX
//Main
Main:
RandMax<-Maximum value
n<-- number of elements
vect<--Array of random values with in the range of RandMax
sort()<--calling sort function to sort the array using divide and conqure
value<-- search element
pos<-- search(value)
if pos not equal to UINT_MAX:
Found at index pos
else:
Invalid Entry