Sortowanie przez scalanie

0

#include <iostream>
using namespace std;
 
void merge(int *,int, int , int );
void mergesort(int *A, int p, int k)
{
    int sr;
    if (p < k)
    {
        sr=(p+k)/2;
        mergesort(A,p,sr);
        mergesort(A,sr+1,k);
        merge(A,p,k,sr);
    }
     return;
}
void merge(int *A, int p, int k, int sr)
{
    int i, j, m, *c;
    c=new int;
    i = p;
    m = p;
    j = sr + 1;
    while (i <= sr && j <= k)
    {
        if (A[i] < A[j])
        {
            c[m] = A[i];
            m=i+1;
            i=i+1;
        }
        else
        {
            c[m] = A[j];
            m=m+1;
            j=j+1;
        }
    }
    while (i <= sr)
    {
        c[m] = A[i];
        m=m+1;
        i=i+1;
    }
    while (j <= k)
    {
        c[m] = A[j];
        m=m+1;
        j=j+1;
    }
    for (i = p; i < m; i++)
    {
        A[i] = c[i];
    }
}
int main()
{
    int n, *A, *b;
    cout<<"Podaj jaka jest wielkosc zbioru:\n ";
    cin>>n;
    A =new int [n];
    b=new int[n];
     
    int i, *c;
    cout<<"Wpisz elementy do posortowania\n";
    for (i = 0; i < n; i++)
    {
        cin>>A[i];
    }
    mergesort(A, 0, n);
    cout<<"Posortowane elementy \n";
    for (i = 0; i < n; i++)
    {
        cout<<A[i]<<"\n";
    }
  cout<<"Wpisz elementy do posortowania\n";
    for (i = 0; i < n; i++)
    {
       cin>>b[i];
    }
    mergesort(b, 0, n);
    cout<<"Posortowane elementy\n";
    for (i = 0; i < n; i++)
    {
        cout<<b[i]<<"\n";
    } 
}

Ktoś mógłby mi pomóc i sprawdzic czemu ten kod nie działa do końca poprawnie? Jest to sortowanie przez scalanie. Przy czym nie zawsze wypisuje odpowiednie wartosci :/

1

Odpal debugger i prześledź działanie krok po kroku. Zmienne o nazwach p, k, c, m zdecydowanie nie zachęcają do analizy.

1

o_O
Najpierw: c=new int;
A kilka linijek niżej c[m] = A[i];
To jest jakieś cudowne rozmnożnie pamięci u ciebie? :D

Heap overflow przez off-by-bardzo-dużo, ale że testujesz pewnie na 5 liczbach to się nie wywala od razu. Jakbyś zrobił test na większych danych to by się program wywalił.

1 użytkowników online, w tym zalogowanych: 0, gości: 1