Question

In: Computer Science

why my code for mergesort always wrong ? void Merge(vector<int>& data, int p, int q, int...

why my code for mergesort always wrong ?

void Merge(vector<int>& data, int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
vector<int>left(n1);
vector<int>right(n2);
for(int i = 0; i < n1; i++)
{
left[i] = data[p + i];
}
for(int j = 0; j < n2; j++)
{
right[j] = data[q+j+1];
}
int i = 0;
int j = 0;
for(int k = p; k <= r; k++)
{
if(left[i] <= right[j])
{
data[k] = left[i];
i += 1;
}
else
{
data[k] = right[j];
j += 1;
}
}
}

void MergeSort(vector<int>& data, int p, int r)
{
if(p<r)
{
int q = (p+r)/2;
MergeSort(data, p, q);
MergeSort(data, q+1, r);
Merge(data, p, q, r);
}

Solutions

Expert Solution

Merge sort updated code:

#include<iostream>
#include<vector>
using namespace std;

void Merge(vector<int> &data, int p, int q, int r) {
        int n1 = q - p + 1;
        int n2 = r - q;

        vector<int> left(n1);
        vector<int> right(n2);

        for (int i = 0; i < n1; i++) {
                left[i] = data[p + i];
        }

        for (int j = 0; j < n2; j++) {
                right[j] = data[q + j + 1];
        }

        // Merge the left & right elements back into data[p..r]
        int i = 0;
        int j = 0;
        int k = p;

        while (i < n1 && j < n2) {
                if (left[i] <= right[j]) {
                        data[k] = left[i];
                        i += 1;
                } else {
                        data[k] = right[j];
                        j += 1;
                }
                k++;
        }

        // Copy the remaining elements of
        // left[], if there are any
        while (i < n1) {
                data[k] = left[i];
                i++;
                k++;
        }

        // Copy the remaining elements of
        // right[], if there are any
        while (j < n2) {
                data[k] = right[j];
                j++;
                k++;
        }

}

void MergeSort(vector<int> &data, int p, int r) {
        if (p < r) {
                int q = (p + r) / 2;

                MergeSort(data, p, q);
                MergeSort(data, q + 1, r);
                Merge(data, p, q, r);
        }
}

// To display the elements in the vector
void print(vector<int> &data, int size) {

        for (int i = 0; i < size; i++)
                cout << data.at(i) << ' ';
        cout << endl;
        cout << endl;
}

// Main to display the given elements before and after sorting
int main() {
        vector<int> data = { 15, 11, 18, 3, 6, 9 };
        int size = data.size();

        cout << "Elements before sorting: ";
        print(data, size);

        MergeSort(data, 0, size - 1);

        cout << "Elements after sorting: ";
        print(data, size);
        return 0;
}

Output of the above program:

Elements before sorting: 15 11 18 3 6 9 

Elements after sorting: 3 6 9 11 15 18

Note:

  • In the above code headers are included
  • The function print is added to display the elements before and after sorting
  • Main function is added to the code
  • In the Merge function, for loop used to merge is replaced with the below code to merge all the elements after sorting
// Merge the left & right elements back into data[p..r]
        int i = 0;
        int j = 0;
        int k = p;

        while (i < n1 && j < n2) {
                if (left[i] <= right[j]) {
                        data[k] = left[i];
                        i += 1;
                } else {
                        data[k] = right[j];
                        j += 1;
                }
                k++;
        }

        // Copy the remaining elements of
        // left[], if there are any
        while (i < n1) {
                data[k] = left[i];
                i++;
                k++;
        }

        // Copy the remaining elements of
        // right[], if there are any
        while (j < n2) {
                data[k] = right[j];
                j++;
                k++;
        }

Related Solutions

Question 31 Given the code snippet below, what prints? void fun(int *p) { int q =...
Question 31 Given the code snippet below, what prints? void fun(int *p) { int q = 10; p = &q; } int main() { int r = 20; int *p = &r; fun(p); cout << *p; return 0; } Question 31 options: 10 20 compiler error Runtime error Question 32 A union’s members are exactly like the members of a Structure. Question 32 options: True False Question 33 Given the code below, what are the errors. #include <iostream> using namespace...
Why is my C code counter returning the wrong output? void removeLn(char *tPtr) { for (;...
Why is my C code counter returning the wrong output? void removeLn(char *tPtr) { for (; *tPtr != '\0'; tPtr++) { if (*tPtr == '\n') { *tPtr = '\0'; } } } This is a method I wrote that essentially replaces the \n in a text file with a null. int counter(FILE *filePtr) { char ln[length]; int counter = 0; while (fgets(ln, length, filePtr) != NULL) { char *r;    for (r = ln; *r != '\0';) { while (isspace(*r))...
   private static void merge(int arr[], int l, int m, int r) {        //...
   private static void merge(int arr[], int l, int m, int r) {        // Find sizes of two subarrays to be merged        int n1 = m - l + 1;        int n2 = r - m;        /* Create temp arrays */        int L[] = new int[n1];        int R[] = new int[n2];        /* Copy data to temp arrays */        for (int i = 0; i...
What is the ouput of the following code? void loop(int num) { for(int i = 1;...
What is the ouput of the following code? void loop(int num) { for(int i = 1; i < num; ++i) { for(int j = 0; j < 5; ++j) { cout << j; } } } int main() { loop(3); return 0; }
Please explain this code line by line void printperm(int *A,int n,int rem,int j) {    if(n==1)...
Please explain this code line by line void printperm(int *A,int n,int rem,int j) {    if(n==1)       {        for(int k=0;k<j;k++)        cout<<A[k]<<" + ";        cout<<rem<<"\n";        return;       }     for(int i=0;i<=rem;i++)    {          if(i<=rem)          A[j]=i;          printperm(A,n-1,rem-i,j+1);    } }
public void printQueue(DoublyLinkedQueue<Integer> Q){ int len = Q.size(); int k = 0; for (int i=0; i...
public void printQueue(DoublyLinkedQueue<Integer> Q){ int len = Q.size(); int k = 0; for (int i=0; i < len; ++i){ k = Q.dequeue(); Q.enqueue(k);    System.out.println(Q.dequeue()); } } What is the complexity of this code? Select one: a. O(N), N = k b. Q(1) c. Q(N2), N = Q.size() d. O(M), M = Q.size() e. None of the alternatives is correct. which one?
Part 1.1 Write a function whose prototype is void exchange ( /*inout*/ int *p, /*inout*/ int...
Part 1.1 Write a function whose prototype is void exchange ( /*inout*/ int *p, /*inout*/ int *q ) that takes two pointers to integer variables and exchanges the values in these variables. Part 1.2 Write a function whose prototype is char lastChar ( /*in*/ const char *str ) that takes a nonempty C-String as parameter and returns the last character in the string. For example the call lastChar ("srjc") will return the character c. Part 1.3 Define an array of...
I have an unexpected indent with my python code. please find out whats wrong with my...
I have an unexpected indent with my python code. please find out whats wrong with my code and run it to show that it works here is the code : def main(): lis = inputData() customerType = convertAcct2String(lis[0]) bushCost = getBushCost(lis[0],int(lis[1],10)) flowerCost = getFlowerBedCost(int(lis[2],10),int(lis[3],10)) fertiCost = getFertilCost(int(lis[4],10)) totalCost = calculateBill(bushCost,fertiCost,flowerCost) printReciept(customerType,totalCost,bushCost,fertiCost,flowerCost) def inputData(): account, number_of_bushes,flower_bed_length,flower_bed_width,lawn_square_footage = input("Please enter values").split() return [account, number_of_bushes,flower_bed_length,flower_bed_width,lawn_square_footage] def convertAcct2String(accountType): if accountType== "P": return "Preferred" elif accountType == "R": return "Regular" elif accountType == "N": return...
hi i do not know what is wrong with my python code. this is the class:...
hi i do not know what is wrong with my python code. this is the class: class Cuboid: def __init__(self, width, length, height, colour): self.__width = width self.__length = length self.__height = height self.__colour = colour self.surface_area = (2 * (width * length) + 2 * (width * height) + 2 * (length * height)) self.volume = height * length * width def get_width(self): return self.__width def get_length(self): return self.__length def get_height(self): return self.__height def get_colour(self): return self.__colour def set_width(self,...
My current code that is not working correctly #include<stdio.h> #include<math.h> int main() { //variable declaration int...
My current code that is not working correctly #include<stdio.h> #include<math.h> int main() { //variable declaration int a,b,c,D,n; double x1,x2; double realPart, imagPart; do { // this set of code blocks prompts a message to the user and then read the integer entered and stores it as an integer printf("Enter a value for a:\n"); scanf("%d",&a); printf("Enter a value for b:\n"); scanf("%d",&b); printf("Enter a value for c:\n"); scanf("%d",&c); printf("You entered the Equation \n"); printf("%dx^2%+dx%+d=0\n",a,b,c); D = b*b - 4*a*c;    if (D<0)...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT