Merge sort.

0

Witam, próbuje sam zaimplementować sortowanie przez scalanie, niestety gdzieś robię błąd.

void merge(int *tab, int p, int mid, int k)
{
    //p,k - granice sortowanej aktulnie podtablicy
    //mid - srodek tablicy, granica kazdej z podtablic przy podziale na pol

    //jedna tablica od p do mid, druga od mid do k

    int *tmp = new int[k-p+1];

    int i=p, j=mid+1; //iteratory dla pierwszej i drugiej czesci tablicy
    int m=0; //iterator dla tablicy pomocniczej

    //mid - p rozmiar 1. tab
    //k - mid rozmiar 2. tab

    while (i!=mid+1 && j!=k+1) //iterator dochodzi do ostatniego elementu w jednej z tablic
    {
        if (tab[i]<tab[j])  tmp[m++]=tab[i++];
        else tmp[m++]=tab[j++];
    }

    if (i==mid && j==k) for (int l=p, m=0; l<k+1; l++, m++) tab[l]=tmp[m];
    if (i==mid+1) for (j; j<k+1; j++, m++) tmp[m]=tab[j];
    else if (j==k+1) for(i; i<mid+1; i++, m++) tmp[m]=tab[i];

    for(int jk=0; jk<k-p+1; jk++) cout<<tmp[jk]<<' ';
    cout<<"\n";

    for (int l=p, m=0; l<=k+1; l++, m++) tab[l]=tmp[m]; //spisujemy dane posortowane z tablicy pomocniczej
    //delete tmp;

    return;
}

void mergeSort(int *tab, int p, int k)
{
    int mid=(p+k)/2;

    if(p!=k)
    {
        mergeSort(tab, p, mid); //sortujemy lewa czesc tablicy
        mergeSort(tab, mid+1, k); //sortujemy prawa czesc tablicy
        merge(tab, p, mid, k); //scalamy posortowane czesci
    }
    return;
}

Przy próbie sortowania tablicy większej niż dwuelementowa dostaję trochę śmieci z pamięci i część posortowanej tablicy. Gdzie mogłem zrobić błąd?

0

Problem rozwiązany:P Błąd był banalny ale takie zawsze najtrudniejsze do znalezienia:)

for (int l=p, m=0; l<=k+1; l++, m++) tab[l]=tmp[m]; //spisujemy dane posortowane z tablicy pomocniczej 

W tym miejscu spisuję część danych z tablicy pomocniczej do głównej, część która jest posortowana. Tutaj spisuję o jeden element za dużo

l<=k+1 

i jest nim właśnie śmieć z pamięci jako, że tablica nie jest wyzerowana:) Może komuś w dalekiej przyszłości to zaoszczędzi trochę nerwów.

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