CREATE DETAILED PSEUDOCODE FOR THE FOLLOWING SOURCE CODE: #include <algorithm> #

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

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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