MergeSort с динамическими массивами - PullRequest
Новая
       0

MergeSort с динамическими массивами

0 голосов
/ 18 октября 2019

Я пытаюсь реализовать функцию mergeSort, которая возвращает динамический массив типа intervalo_t. На самом деле, функция работает хорошо, проблема у меня заключается в том, что когда я запускаю Valgrind для проверки потери памяти, оказывается, что я немного теряю.

Определение Intervalo_t: 

struct intervalo_t {
    nat inicio;
    nat fin;
};

Это код: 

intervalo_t* mergeSort(intervalo_t *intervalos, nat n)
{   
    intervalo_t* ret=new intervalo_t[n];
    if(n==2){
        if (intervalos[0].fin>intervalos[1].fin){
            ret[0]=intervalos[1];
            ret[1]=intervalos[0];
        }else{
            ret[0]=intervalos[0];
            ret[1]=intervalos[1];
        }
    //caso base
    }else if (n==1){
        ret[0]=intervalos[0];
    //caso base
    }else{
        nat k=0;        
        if((n%2)!=0){
            k=1;
        }//Si es par o no
        intervalo_t* interA =new intervalo_t[n/2 + k];
        intervalo_t* interB =new intervalo_t[n/2];
        for (nat i=0; i<n/2; i++){
            interA[i]=intervalos[i];
            interB[i]=intervalos[i+(n/2)];
        }//for
        if (k==1){ 
            interA[(n/2)]=intervalos[n-1];
        }
        interA=mergeSort(interA, n/2 + k);
        interB=mergeSort(interB, n/2);
        nat i=0;
        nat j=0;
        nat r=0;
        while((i<((n/2)+k)) && (j<(n/2))){
            if (interA[i].fin>interB[j].fin){
                ret[r]=interB[j];
                j++;
            }else{
                ret[r]=interA[i];
                i++;
            }
            r++;
        }
        while(i<(n/2)+k){
            ret[r]=interA[i];
            i++;
            r++;
        }
        while(j<(n/2)){
            ret[r]=interA[j];
            i++;
            j++;
        }
        delete[] interA;
        delete[] interB;
    //recursion
    }
    return ret; 
}

А это вывод Valgrind: 

==15556== 
==15556== HEAP SUMMARY:
==15556==     in use at exit: 24 bytes in 2 blocks
==15556==   total heap usage: 12 allocs, 10 frees, 77,959 bytes allocated
==15556== 
==15556== 8 bytes in 1 blocks are definitely lost in loss record 1 of 2
==15556==    at 0x4C2F06F: operator new[](unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==15556==    by 0x401536: mergeSort(intervalo_t*, unsigned int) (intervalos.cpp:26) 
==15556==    by 0x4017C3: max_cantidad(intervalo_t*, unsigned int) (intervalos.cpp:67)
==15556==    by 0x401130: main (principal.cpp:170)
==15556== 
==15556== 16 bytes in 1 blocks are definitely lost in loss record 2 of 2
==15556==    at 0x4C2F06F: operator new[](unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==15556==    by 0x401509: mergeSort(intervalo_t*, unsigned int) (intervalos.cpp:25)
==15556==    by 0x4017C3: max_cantidad(intervalo_t*, unsigned int) (intervalos.cpp:67)
==15556==    by 0x401130: main (principal.cpp:170)
==15556== 
==15556== LEAK SUMMARY:
==15556==    definitely lost: 24 bytes in 2 blocks
==15556==    indirectly lost: 0 bytes in 0 blocks
==15556==      possibly lost: 0 bytes in 0 blocks
==15556==    still reachable: 0 bytes in 0 blocks
==15556==         suppressed: 0 bytes in 0 blocks
==15556== 
==15556== For lists of detected and suppressed errors, rerun with: -s
==15556== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

Я запустил valgrind с: 

valgrind --leak-check=full ./myFile <test.in

Test.in: 

mergeSort
15
30
45

Заранее спасибо за помощь!

1 Ответ

1 голос
/ 18 октября 2019

Проблема в том, что выделенная здесь память: 

intervalo_t* interA =new intervalo_t[n/2 + k];
intervalo_t* interB =new intervalo_t[n/2];

просачивается при перезаписи этих указателей здесь: 

interA=mergeSort(interA, n/2 + k);
interB=mergeSort(interB, n/2);

Редко хорошей идеей является повторное использование переменных для несколькихДля рекурсивных результатов используйте отдельные переменные: 

intervalo_t* resultA=mergeSort(interA, n/2 + k);
intervalo_t* resultB=mergeSort(interB, n/2);

, а затем используйте их для слияния (и не забудьте их освободить).
Я бы также рекомендовал избавиться от входных данных сразу после повторения, чтобы выне забывайте об этом.

Или вы можете использовать std::vector и избавить себя от головной боли.

...