Sample Data Structures Questions Chapter 13 Sorting provide correct short answer
ID: 3721229 • Letter: S
Question
Sample Data Structures Questions
Chapter 13
Sorting
provide correct short answer in c++
10. Implement the following function:
void merge(int data[ ], size_t n1, size_t n2);
// Precondition: The first n1 elements of data are sorted, and the next n2 elements of data are sorted (from smallest to largest).
// Postcondition: The n1+n2 elements of data are now completely sorted.
14. Suppose that you implement quick sort non-recursively using a stack, as in your last programming assignment. You use your algorithm to sort an array of 100 items, and at the start of the final iteration of the while loop, the stack contains just two numbers: 10 (on top) and 90 (on bottom). Write one or two clear sentences to describe which parts of the array are sorted at this point, and which parts of the array remain to be sorted.
Explanation / Answer
10)
void merge(int data[],size_t n1,size_t n2)
{
//Create two temp array
int a[n1],b[n2];
//Copy element to ni and n2
for(int i=0;i<n1;i++)
{
a[i]=data[i];
}
for(int j=0;j<n2;j++)
{
b[j]=data[n1+j];
}
int i=0,j=0,k=0;
//merge a and b array to data
while(i<n1 && j<n2)
{
if(a[i]<b[j])
{
data[k]=a[i];
i++;
}
else
{
data[k]=b[j];
j++;
}
k++;
}
}
14) Only partition and sort is going to evaluate between stack top and bottom index. As it contains 10 and 90, that means this range of index need to be sorted. So Array is sorted from 0 to 9 index and 91 to 99(100-1) index.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.