Что не так с моей программой сортировки слиянием C ++? - PullRequest
Новая
       11

Что не так с моей программой сортировки слиянием C ++?

0 голосов
/ 21 марта 2012

Я застрял в тупике с этой реализацией.Моя переменная n2 перезаписывается во время слияния подмассивов, что может быть причиной этого?Я пробовал жестко запрограммировать значения, но это не похоже на работу. 

#include <iostream>
#include <cstdlib>
#include <ctime> // For time(), time(0) returns the integer number of seconds from the     system clock
#include <iomanip>
#include <algorithm> 
#include <cmath>//added last nite 3/18/12 1:14am

using namespace std;

int size = 0;

void Merge(int A[], int p, int q, int r)
{
    int i,
        j,
        k,
        n1 = q - p + 1,
        n2 = r - q;

    int L[5], R[5];

    for(i = 0; i < n1; i++)
        L[i] = A[i];

    for(j = 0; j < n2; j++)
        R[j] = A[q + j + 1];

    for(k = 0, i = 0, j = 0; i < n1  && j < n2; k++)//for(k = p,i = j = 1; k <= r; k++)
    {
        if(L[i] <= R[j])//if(L[i] <= R[j])
        {
            A[k] = L[i++];
        } else {
            A[k] = R[j++];
        }
    }
}

void Merge_Sort(int A[], int p, int r)
{
    if(p < r)
    {
        int q = 0;
        q = (p + r) / 2;
        Merge_Sort(A, p, q);
        Merge_Sort(A, q+1, r);
        Merge(A, p, q, r);
    }
}

void main()
{
    int p = 1,
        A[8];

    for (int i = 0;i < 8;i++) {
        A[i] = rand();
    }
    for(int l = 0;l < 8;l++)
    {
        cout<<A[l]<<"  \n";
    }
    cout<<"Enter the amount you wish to absorb from host array\n\n";
    cin>>size;
    cout<<"\n";
    int r = size; //new addition
    Merge_Sort(A, p, size - 1);

    for(int kl = 0;kl < size;kl++)
    {
        cout<<A[kl]<<"  \n";
    }

}

Ответы [ 3 ]

1 голос
/ 21 марта 2012

Какие инструменты вы используете для компиляции программы?Есть некоторые флаги, которые включают проверки для такого рода вещей в e, .g.gcc (например, -fmudflap, я не использовал его, но это выглядит весьма полезным).

Если вы можете использовать отладчик (например, gdb), вы сможете добавить «просмотр данных» для переменной n2, и отладчик остановит программу всякий раз, когда он обнаруживает что-либо, записывающее в n2.Это должно помочь вам отследить ошибку.Или попробуйте valgrind .

Простой способ временно остановить этот тип ошибки - поместить фиктивные переменные вокруг одной получаемой, поэтому: 

int dummy1[100];
int n2 = r - q;
int dummy2[100];

int L[5], R[5];

Переменныеперебор обычно вызывается написанием кода за пределами массивов.Виновник, вероятно, R[5], потому что это, вероятно, самый близкий.Вы можете заглянуть в макеты, чтобы увидеть, что пишется, и, возможно, сможете сделать вывод из того, что происходит.

Еще один вариант - сделать все массивы огромными, пока вы отслеживаете проблему.Снова установите значения за правильными границами на известное значение и проверьте те значения, которые должны быть неизменными.

Вы можете сделать небольшой макрос для этих проверок и поместить его в любое удобное место.

1 голос
/ 05 июня 2012

Ранее я использовал подобную функцию слияния, и она, похоже, не работает должным образом. Тогда я изменил дизайн, и теперь он работает отлично. Ниже приведено новое определение функции слияния в C ++. 

void merge(int a[], int p, int q, int r){
    int n1 = q-p+1;             //no of elements in first half
    int n2 = r-q;               //no of elements in second half
    int i, j, k;

    int * b = new int[n1+n2];   //temporary array to store merged elements

    i = p;
    j = q+1;
    k = 0;
    while(i<(p+n1) && j < (q+1+n2)){     //merging the two sorted arrays into one
        if( a[i] <= a[j]){
            b[k++] = a[i++];
        }
        else 
            b[k++] = a[j++];
    }

    if(i >= (p+n1))         //checking first which sorted array is finished
        while(k < (n1+n2))      //and then store the remaining element of other 
            b[k++] = a[j++];    //array at the end of merged array.
    else
        while(k < (n1+n2))
            b[k++] = a[i++];

    for(i = p,j=0;i<= r;){      //store the temporary merged array at appropriate  
        a[i++] = b[j++];        //location in main array.
    }

    delete [] b;
}

Надеюсь, это поможет.

0 голосов
/ 21 марта 2012 
void Merge(int A[], int p, int q, int r)
{
    int i,
        j,
        k,
        n1 = q - p + 1,
        n2 = r - q;

    int L[5], R[5];

    for(i = 0; i < n1; i++)
        L[i] = A[i];

Вы выделяете только L[5], но используемая вами граница n1 основана на входах q и p - и вызывающему разрешено вызывать функцию со значениями q и p, которые позволяют писать за пределами L[].Это может проявляться как перезапись любых других автоматических переменных, но поскольку это неопределенное поведение, может произойти практически все.(Включая уязвимости безопасности .)

Я не знаю, каков лучший способ исправить это - я не понимаю, почему у вас есть буферы фиксированной длины в Merge()Я не читал достаточно внимательно, чтобы понять, почему - но вы не должны обращаться к L[i], когда i больше или равно 5.

Весь этот разговор также относится к R[],И, поскольку *A передается в Merge(), имеет смысл убедиться, что ваши обращения к массиву для него также всегда связаны.(Я не заметил, как они выходят за пределы, но так как этот код все равно нуждается в доработке, я не уверен, что стоит внимательно их искать.)

...