Sortowanie przez scalanie

Question

#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,k);
        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: ";
    cin>>n;
    A =new int [n];
    b=new int;
     
    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]<<"";
    }
    cout<<"Wppisz 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]<<"";
    }
     
}

Jest to sortowanie przez scalanie. Niestety nie działa ktoś pomógłby poprawić? Bardzo pilne 

Answer 1

Mi działa.

Comments

Wkleiłam zły kod nie ten co trzeba :/ juz jest inny

Answer 2

• Program odnosi się do niezaalokowanej pamięci ( wskaźnik b nie dostał przydziału pamięci za pomocą operatora new)
• For'y napisane w mainie idą od i == 0 do i == n,  a powinny do i == n - 1.
• Wskaźnik c w funkcji merge nie ma przydzielonej pamięci ( znow brak instrukcji z operatorem new )
• W funkcji mergesort pierwsze wywolanie rekurencyjne ma zle argumenty ( powinno byc mergesort(A,p,sr); )

Po naprawieniu tych błędów wszystko działa, sugestia, to żeby poprawić w wypisywaniu puste cudzyslowy, na cudzyslowy oddzielone spacja, a po wypisywaniu odpowiedzi wypisac '\n' konczace linie.

Comments

Dziękuję pięknie ! Już działa poprawnie.

---

#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;
     
    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";
    }
} 

Mam jeszcze pytanie bo nie wiem czemu jak wpisuje liczby to pierwsza zamienia mi na 0 :/ reszta jest okey 

---

• jest b = new int, a powinno byc b = new int [n] ( 62 linijka )
• jest mergesort( A, 0, n ), a powinno być mergesort( A, 0, n - 1 ) ( 70 linijka i 81 linijka )
• jest c = new int, a powinno byc c = new int [k + 1] ( 20 linijka )
• jest m = i + 1, a powinno byc m = m + 1 ( 29 linijka )

Po tych poprawkach powinno być wszystko dobrze, napisze jeszcze krotki skrypt w bashu, ktory posprawdza, czy wszystko sie dobrze sortuje i jak cos bedzie nie tak, to napisze kolejny komenatrz, ale juz powinno byc  w porzadku. Jeszcze w 59 linijce na koncu stringu do wypisania wkradla sie niepotrzebna spacja =)

---

Super wszystko :D Dziękuję a jakbyś miał wybrac wazniejsze ok 15 linii kodu i uzasadnic czemu je wybrałes to które bys wybrał? Dla mnie caly kod jest wazny i nie jestem pewna co do wyboru