In: Computer Science
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);
}
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:
// 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++;
}