Merge Sort C++

Question

Cześć, mam za zadanie napisać program, który posortuję dwa rosnące ciągi przez scalanie. Posortuje je dopóki pierwszy ciąg nie dobiegnie końca, a następnie dopisze pozostałe wyrazy drugiego ciągu. Niestety z tego co widzę drugi człon funkcji (po pierwszym do - while'u) nie działa poprawnie, bo końcówka sortowania nie dopisuje się (wstawia zazwyczaj losowe liczby) i za Boga nie mogę rozgryźć czemu. 

 

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void scal(int tab[], int p, int g, int k)
{
   int i = p;
    int j = g;
    int n=0;

    int pom[23];

     // sortowanie początków obu ciągów rosnących
    do
    {
        if(tab[i]<=tab[j])
        {
            pom[n]=tab[i];
            i++;
            n++;
        }
        else
        {
            pom[n]=tab[j];
            j++;
            n++;
        }
    }while(i<g||j<=k);

    if(i==g&&j<k)  // dopisanie reszty ciągu
    {
        do
        {
            pom[n]=tab[j];
            j++;
            n++;
        }while(j<=k);
    }
    else if(j==k&&i<g)
    {
        do
        {
            pom[n]=tab[i];
            i++;
            n++;
        }while(i<=g);
    }

    for(int a=0; a<23; a++)
    {
        tab[a]=pom[a];
    }
}

int main()
{
    srand(time(0));

    int tab[23];
    int p, g, k;

    tab[0]=rand()%10;
    for(int i=1; i<=11; i++)
    {
        tab[i]=tab[i-1]+(rand()%10) + 1;
    }

    tab[12]=rand()%10;
    for(int i=13; i<=22; i++)
    {
        tab[i]=tab[i-1]+(rand()%10) + 1;
    }

/*
        for(int i=0; i<=22; i++)
    {
        cout << tab[i] << " ";
    }

    cout << endl;
*/
    g=12;
    p=0;
    k=22;

    scal(tab, p, g, k);

    for(int i=0; i<=22; i++)
    {
        cout << tab[i] << " ";
    }
    cout << endl;

}

Pomoże ktoś? Dzięki

Answer 1

w 30 linijce zmien sobie warunek zakonczenia petli z || na && w przeciwnym razie wyjdziesz poza któryś z ciągów.

while(i<g&&j<=k);

w linijce 32

if(i>=g)

przypadek gdy dotarłeś do końca 1 ciągu

w linijce 41

else if(j>=k)

przypadek gdy dotarleś do końca 2 ciągu wcześniej

Comments

ale jeśli się nie myle && znaczy "i", więc oba warunki musiały by być spełnione?

---

Tak, pętla pętla bedzie się wykonywać dopóki będzie możliwe przejście do następnej liczby ciągu gdy którekolwiek liczby (tzn te z ciągu 1 lub 2) sie skończą warunek zwróci fałsz i pętla się zakończy.