Merge Sort - wychodzenie poza zakres

2011-03-15 14:05
0

Witam, mam problem z zaimplementowaniem Merge Sortu. Gdzieś mi wychodzi poza zakres, bo w ogóle zmienia wartości w tablicy..

#include<iostream>
#include<ctime>

using namespace std;

void merge(int *tab, int pocz, int sr, int kon)
{
    int n1 = sr-pocz+1; // n1 i n2 to wielkosci tablic pomocniczych
    int n2 = kon-sr; 
    int *L = new int [n1]; //tablica lewa i prawa przechowuja odpowiednio lewa i prawa czesc podzialu
    int *R = new int [n2];

    for (int i=0; i<n1; i++) //kopiowanie podzielonej tablicy do lewej i prawej
        L[i] = tab[pocz+i];
    for (int i=0; i<n2; i++)
        R[i] = tab[sr+1+i];

    int i = 0;
    int j = 0;

    for (int k=0; k<=kon; k++) //scalenie do tablicy wejsciowej
        if (L[i] <= R[j]) 
            tab[k] = L[i++]; //wpisujemy z L poczym zwiekszamy indeks i 
        else 
            tab[k] = R[j++];

    delete L;
    delete R;
}

void MergeSort (int *tab, int pocz, int kon)
{
    int tmp;
    if (pocz < kon)
    {
        tmp = (pocz+kon)/2;
        MergeSort(tab, pocz, tmp);
        MergeSort(tab, tmp+1, kon);
        merge(tab, pocz, tmp, kon);
    }
}

int main ()
{
    cout << "Podaj wielkosc sortowanej tablicy: ";
    int size;
    cin >> size;

    int *t = new int [size];

    srand(time(0));
    for (int i=0; i<size; i++)
        t[i] = rand()%101;

    cout << "Wylosowana tablca: " << endl;
    for (int i=0; i<size; i++)
        cout << t[i] << "   ";
    cout << "\n\n Posortowana tablica: \n";

    MergeSort(t, 0, size);

    for (int i=0; i<size; i++)
        cout << t[i] << "   ";

    getchar();
} 

Pozostało 580 znaków

2011-03-15 14:58
0

Zastanów się co twój program zrobi z prostą tablicą:
... Tb[]={4,5,2,3};
Podzieli to na:
L[]={4,5};
R[]={2,3};
A przy zapisie
wpiszę 2,3 a w kolejnym kroku będzie porównywać L[0] z nieistniejącym R[2].


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2011-03-15 15:54
0

no dobra, ale nawet pierwsze dwie się nie wpisują.. zresztą poprawiłem to - dodałem wartownika. Do L i R dodałem jeden indeks i wpisałem do nich sume z przedostatnich indeksów L i R. W merge sorcie podzielone tablice są posortowane, więc nigdy ta wartość nie zostanie wpisana (bo będzie największa, a nie dojdzie do niej bo wejściowa tablica jest za mała)

I w sumie teraz to wywala program: "HEAP CORRUPTION DETECTED (...) CRT detected that wrote to memory after end of the heap buffer".
sam wartownik :

L[n1+1] = L[n1] + R[n2];
R[n1+1] = L[n1] + R[n2]; 

i cały poprawiony kod. Teraz na pewno nie występuje błąd który pokazałeś (przynajmniej wg mnie ;) )

#include<iostream>
#include<ctime>

using namespace std;

void merge(int *tab, int pocz, int sr, int kon)
{
    int n1 = sr-pocz+1; // n1 i n2 to wielkosci tablic pomocniczych
    int n2 = kon-sr; 
    int *L = new int [n1+1]; //tablica lewa i prawa przechowuja odpowiednio lewa i prawa czesc podzialu
    int *R = new int [n2+1];

    for (int i=0; i<n1; i++) //kopiowanie podzielonej tablicy do lewej i prawej
        L[i] = tab[pocz+i];
    for (int i=0; i<n2; i++)
        R[i] = tab[sr+1+i];

    L[n1+1] = L[n1] + R[n2]; //Wartownik - dodaje po jednym indeksie do kazdej z tablic, i przypisuje do niej sume najwiekszej watrtosci - na pewno nie zostana wpisane do tab
    R[n1+1] = L[n1] + R[n2];

    int i = 0;
    int j = 0;

    for (int k=0; k<=kon; k++) //scalenie do tablicy wejsciowej
        if (L[i] <= R[j]) 
            tab[k] = L[i++]; //wpisujemy z L poczym zwiekszamy indeks i 
        else 
            tab[k] = R[j++];

    delete L;
    delete R;
}

void MergeSort (int *tab, int pocz, int kon)
{
    int tmp;
    if (pocz < kon)
    {
        tmp = (pocz+kon)/2;
        MergeSort(tab, pocz, tmp);
        MergeSort(tab, tmp+1, kon);
        merge(tab, pocz, tmp, kon);
    }
}

int main ()
{
    cout << "Podaj wielkosc sortowanej tablicy: ";
    int size;
    cin >> size;

    int *t = new int [size];

    srand(time(0));
    for (int i=0; i<size; i++)
        t[i] = rand()%101;

    cout << "Wylosowana tablca: " << endl;
    for (int i=0; i<size; i++)
        cout << t[i] << "   ";
    cout << "\n\n Posortowana tablica: \n";

    MergeSort(t, 0, size);

    for (int i=0; i<size; i++)
        cout << t[i] << "   ";

    getchar();
} 

Pozostało 580 znaków

2011-03-15 17:14
L[n1+1] = L[n1] + R[n2];
R[n1+1] = L[n1] + R[n2];

tu wyłazisz poza przydzieloną pamięć.

Lepiej zrób to w piętle kopiującej:

int k=0;
while((i<n1)&&(j<n2)) tab[k++]=(L[i]<=R[j]?L[i++]:R[j++]);
while(i<n1) tab[k++]=L[i++];
while(j<n2) tab[k++]=R[j++];

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2011-03-15 19:49
0

dzięki wszystko działa :) tylko nie int k = 0, a int k = pocz
a i jest jeszcze mały błąd - na przyszłość może komuś się przyda. W wywołaniu sortowania jest

MergeSort(t,0,size) 

, a powinno być:

MergeSort(t,0,size-1) 
edytowany 1x, ostatnio: chrisck, 2011-03-15 20:06
Błędów tu o wiele więcej, mimo że wszystko działa. Chodzi o to że bardzo dużo jest przydzielania i zwalniania pamięci, miało by sens przydzielić od razu dodatkową tablice rozmiarem sortowanej i to do niej zapisywać wyniki. Znacznie przyspieszyło by sprawdzanie czy trzeba sortować nie na początku funkcji MergeSort, zaś przed każdym wywołaniem. Kopiowanie wartości warto zrobić za pomocą memcpy, wszak szybciej niż za pomocą pętli. Całość warto przerobić na odwołania wskaźnikowe. - _13th_Dragon 2011-03-15 20:13

Pozostało 580 znaków

Liczba odpowiedzi na stronę

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