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))...
Iterative Merge Sort is not working #include #include #include int* b; void merge(int a[], int left,...
Iterative Merge Sort is not working #include #include #include int* b; void merge(int a[], int left, int mid, int right) {    int i = left, j = mid + 1, k = left;    while (i <= mid && j <= right)    {        if (a[i] < a[j])            b[k++] = a[i++];        else            b[k++] = a[j++];    }    for (; i <= mid; i++)    {        b[k++]...
   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...
#include<vector> #include<iostream> using namespace std; void println(const vector<int>& v) {    for (int x : v)...
#include<vector> #include<iostream> using namespace std; void println(const vector<int>& v) {    for (int x : v)        cout << x << " ";    cout << endl; } void println(const vector<string>& v) {    for (const string& x : v)        cout << " "<< x << " ";    cout << endl; } int main() {    vector<int> v0;    cout << "An empty vector of integers: ";    println(v0);    vector<int> v1(3);    cout << "A...
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);    } }
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT