Сортировка слиянием с рекурсией

    /*
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];

Определите «не работает». Нет выхода? Неверный вывод? Сбои? Не компилируется?

9769953 15.08.2018 10:07

Вы пробовали включать предупреждения компилятора и читали их? Это должно выявить проблему.

9769953 15.08.2018 10:10

С самого начала это недопустимый C++. Увеличьте строгость вашего компилятора (используя -pedantic на clang / gcc).

Konrad Rudolph 15.08.2018 11:22

Пожалуйста, редактировать ваш вопрос, чтобы показать нам, какую отладку вы выполнили. Я ожидаю, что вы запустили свой минимальный воспроизводимый пример в Valgrind или аналогичном средстве проверки, а также провели исследование с помощью отладчика, такого как GDB, например. Убедитесь, что вы также включили полный набор предупреждений компилятора. Что вам сообщили инструменты и какая информация в них отсутствует? И прочитайте Как отлаживать небольшие программы Эрика Липперта.

Toby Speight 15.08.2018 17:10

Такие вещи, как int L[n1],R[n2];, недопустимы для C++, потому что В C++ нет массивов переменной длины. Такой код иногда может компилироваться из-за нестандартного расширения GCC. Вы должны сделать ваши массивы фиксированного размера или использовать std::vector.

BessieTheCookie 15.08.2018 19:49
Стоит ли изучать PHP в 2026-2027 годах?
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
5
97
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

В вашей логике слияния есть проблемы. Подумайте, что происходит, когда вы хотите объединить первые два элемента в массиве. В этом случае 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 уже являются целыми числами, поэтому компилятор использует целочисленное деление, давая целочисленный результат.

Я обновил свой ответ, добавив еще несколько предложений вверху

Martin Cook 17.08.2018 10:50

Другие вопросы по теме