/*
This code is Written by Shankhadeep Dey
(15th Aug 2018)
*/
#include<iostream>
using namespace std;
void merge(int a[],int p,int q,int r)
{
int n1,n2,j,i,k;
n1= q-p+1;
n2= r-q;
int L[n1],R[n2];
for (i = 0; i < n1-1; ++i)
L[i]=a[p+i-1];
for (j = 0; j < n2-1; ++j)
R[j]=a[q+j];
L[n1]=1e9;
R[n2]=1e9;
i=0;
j=0;
for (k = p; k < r; ++k)
{
if (L[i]<=R[j])
{
a[k]=L[i];
i++;
}
else
{
a[k]=R[j];
j++;
}
}
while (i < n1)
{
a[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
a[k] = R[j];
j++;
k++;
}
}
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);
}
}
int main()
{ int w[4] = {4,3,21,5};
mergeSort(w,0,3);
for (int i = 0; i < 4; ++i)
{
cout<<w[i]<<" ";
}
cout<<endl;
}
Кто-нибудь может сказать мне, почему эта сортировка не работает?
Я пробовал этот алгоритм из книги «Введение в алгоритм», но я не уверен, почему этот код не работает. Я пробовал искать в Интернете сортировку слиянием и нашел так много вещей, но я точно хочу знать, что не так с моим кодом.
Результат: -0 1000000000 1 1000000000 (что неверно) .
Это предупреждение, которое я получаю
mergeSort.cpp: In function ‘void merge(int*, int, int, int)’:
mergeSort.cpp:12:10: warning: ISO C++ forbids variable length array ‘L’ [-Wvla]
int L[n1],R[n2];
^
mergeSort.cpp:12:16: warning: ISO C++ forbids variable length array ‘R’ [-Wvla]
int L[n1],R[n2];
Вы пробовали включать предупреждения компилятора и читали их? Это должно выявить проблему.
С самого начала это недопустимый C++. Увеличьте строгость вашего компилятора (используя -pedantic на clang / gcc).
Пожалуйста, редактировать ваш вопрос, чтобы показать нам, какую отладку вы выполнили. Я ожидаю, что вы запустили свой минимальный воспроизводимый пример в Valgrind или аналогичном средстве проверки, а также провели исследование с помощью отладчика, такого как GDB, например. Убедитесь, что вы также включили полный набор предупреждений компилятора. Что вам сообщили инструменты и какая информация в них отсутствует? И прочитайте Как отлаживать небольшие программы Эрика Липперта.
Такие вещи, как int L[n1],R[n2];, недопустимы для C++, потому что В C++ нет массивов переменной длины. Такой код иногда может компилироваться из-за нестандартного расширения GCC. Вы должны сделать ваши массивы фиксированного размера или использовать std::vector.





В вашей логике слияния есть проблемы. Подумайте, что происходит, когда вы хотите объединить первые два элемента в массиве. В этом случае p = 0, q = 0 и r = 1. В этом случае n1 = 0, и следующий цикл никогда не выполняется:
for (i = 0; i < n1-1; ++i)
L[i]=a[p+i-1];
То же и со следующей петлей. Хуже того, если бы вы исправили это, изменив n1-1 на n1, тогда в первой итерации p+i-1 был бы -1, что вызвало бы больше проблем.
Если вы хотите обмануть, сравнивая с рабочим решением, я считаю, что он есть на Как реализовать сортировку слиянием из «Введение в алгоритмы» Кормена и Ко.
В более общем плане я бы предложил работать с построчным отладчиком (либо с помощью gdb, либо с использованием IDE, например Eclipse), что позволит вам поэтапно выполнять код, проверяя, что выполняется, когда и какие значения переменных находятся на каждом шаге. Это значительно упрощает диагностику подобных ошибок.
(Примечание: эта проблема была исправлена при редактировании вопроса).
Проблема в этих строках:
for (int i = 0; i < n2-1; ++i)
R[j]=a[q+j];
Либо используйте j, либо i, но не оба сразу. В настоящий момент вы используете неинициализированное значение j.
Кстати, вы дважды объявляете переменные i и j (один раз в верхней части функции и еще раз в цикле for). Это не останавливает работу программы, но наличие двух переменных с одинаковыми именами в разных областях - не лучшая практика, так как это может вызвать путаницу.
Также в этой строке:
q= (int)(p+r)/2;
Компонент (int) ничего не делает и может ввести читателя в заблуждение. p и r уже являются целыми числами, поэтому компилятор использует целочисленное деление, давая целочисленный результат.
Я обновил свой ответ, добавив еще несколько предложений вверху
Определите «не работает». Нет выхода? Неверный вывод? Сбои? Не компилируется?