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...
Why is 1 example of my code failing? def current_player_score(score_one: int, score_two: int,current_player: str) -> int:...
Why is 1 example of my code failing? def current_player_score(score_one: int, score_two: int,current_player: str) -> int: """Return <score_one> if the <current_player> represents player one, or <score_two> if the <current_player> represents player two. >>> current_player_score(2, 4, "Player one") 2 >>> current_player_score(2, 3, "Player two") 3 """ if current_player == PLAYER_ONE: return score_one return score_two
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; }
Given the root C++ code: void sort() {    const int N = 10;    int...
Given the root C++ code: void sort() {    const int N = 10;    int x[N];    for(int i = 0; i < N; i++)    {        x[i] = 1 + gRandom-> Rndm() * 10;        cout<<x[i]<<" "; }    cout<<endl;    int t;       for(int i = 0; i < N; i++)    {    for(int j = i+1; j < N; j++)    {        if(x[j] < x[i])        {   ...
Consider the following code: void swap(int arr[], int i, int j) {        int temp = arr[i];...
Consider the following code: void swap(int arr[], int i, int j) {        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp; } void function(int arr[], int length) {        for (int i = 0; i<length / 2; i++)               swap(arr, i, (length / 2 + i) % length); } If the input to the function was int arr[] = { 6, 1, 8, 2, 5, 4, 3, 7 }; function(arr,8); What values would be stored in the array after calling the...
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...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT