Write a merge sort method given two other methods that must be done recursively
ID: 645205 • Letter: W
Question
Write a merge sort method given two other methods that must be done recursively without any loops (for, while, etc.)
/**
* Returns a new queue containing the elements from the input queue
* in sorted order.
*
* Do not modify the input queue! Work on a copy of the input.
*
* Implement this method recursively:
*
* In the base case, return the sorted queue.
*
* Otherwise:
*
* First, divide the input queue into two smaller output queues.
*
* Then, recursively mergeSort each of these smaller queues.
*
* Finally, return the result of merging these two queues.
*
* @parameter queue an input queue
* @return a sorted copy of the input queue
*/
public Queue mergeSort(Queue queue) {
The two methods given are:
void divide(Queue input, Queue output1, Queue output2) {
This takes the input Queue parameter and divides it evenly into the two output queues. For example, if the input queue has 8 elements, 4 elements will go in output1 and 4 into output2.
Queue merge(Queue input1, Queue input2) {
This method returns a new Queue that is declared within the method that combines the two input queues. What this method also does sort the values of each input queue and then puts them into the new returned output queue. In other words, it checks the top or first value of each input queue, whichever one is smaller, will be enqueued into the output queue that will be returned.
Using those two methods provided, how do I write the mergeSort method using recursion and no loops.
Explanation / Answer
#include <stdio.h>
#include <conio.h>
void Mergesort(int[],int,int);
void Merge(int[],int,int,int);
void main()
{
int x[20],n;
int i=0;
printf("enter the size of array ");
scanf("%d",&n);
printf("enter array elements");
while(i<n)
{
scanf("%d",&x[i]);
i++
}
printf("Array before sorting");
while(i<n)
{
printf("%d",x[i]);
i++;
}
Mergesort(x[],0.n-1)
printf("array after sorting");
while(i<n)
{
printf("%d",x[i]);
i++;
}
}
void Mergesort(int a[],int p,int r)
{
int q;
if(p<r)
{
q=(p+r)/2;
Mergesort(a,p,q);
Mergesort(a,q+1,r);?
Merge(a,p,q,r);
}
}
void Merge(int a[],int p,int q,int r)
{
int b[20],l1,r1,i;
l1=p;
r1=q+1;
i=p;
while((l1<=q) && (r1<=r))
{
if(a[l1]<a[r1])
{
b[i]=a[l1];
l1=l1+1;
i=i+1;
}
else
{
b[i]=a[r1];
r1=r1+1;
i=i+1;
}
}
while(l1<=q)
{
b[i]=a[l1];
l1=l1+1;
i=i+1;
}
while(r1<=r)
{
b[i]=a[r1];
r1=r1+1;
i=i+1;
}
for(i=p;i<=r;i++)
{
a[i]=b[i];
printf("%d",a[i]);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.