Повреждение кучи при освобождении памяти в рекурсивной функции

Question

Я реализую алгоритм, чтобы выбрать Kth самый маленький элемент массива. до сих пор, когда я пытался освободить кучу памяти, я получил эту ошибку: CRT обнаружил, что приложение записало в память после завершения буфера кучи...

int SEQUENTIAL_SELECT(int *S , int k , int n)
{
    if(n<=Q) // sort S and return the kth element directly
    {
        qsort(S,n,sizeof(int),compare);
        return S[k];
    }
    // subdivide S into n/Q subsequences of Q elements each
    int countSets = ceil((float)n/(float)Q);

    //sort each subsequnce and determine its median
    int *medians = new int[countSets];
    for(int i=0;i<countSets;i++)
    {
        if(i==countSets-1) 
        {
            int size = Q - (n%Q);
            qsort(&S[Q*i],size,sizeof(int),compare);
            medians[i] = S[i*Q+size/2];
            continue;
        }
        qsort(&S[Q*i],Q,sizeof(int),compare);
        medians[i] = S[i*Q+Q/2]; 
    }

    // call SEQUENTIAL_SELECT recursively to find median of medians 
    int m = SEQUENTIAL_SELECT(medians,countSets/2,countSets);
    delete[] medians;
    int size = (3*n)/4;

    int* s1 = new int[size]; // contains values less than m
    int* s3 = new int[size]; // contains values graten than m

    for(int i=0;i<size;i++)
    {
        s1[i] = INT_MAX;
        s3[i] = INT_MAX;
    }
    int i1=0;
    int i2=0;
    int i3=0;
    for(int i=0;i<n;i++)
    {
        if(S[i]>m)
            s3[i3++] = S[i];
        else if(S[i]<m)
            s1[i1++] = S[i];
        else
            i2++; // count number of values equal to m
    }

    if( i1>=k )
        m = SEQUENTIAL_SELECT(s1,k,i1);
    else if( i1+i2+i3 >= k)
        m = SEQUENTIAL_SELECT(s3,k-i1-i2,i3);


    delete[] s3;
    delete[] s1;

    return m;
}

Answer 1

@Dcoder, конечно, правильно, что Q - n%q это неверно. Так должно быть n%Q, Кроме того, вычисление size = (3*n)/4 не является надежным; попробуйте это с n = 6 (если предположить, что Q на самом деле 5) заданный вектор [1, 2, 3, 4, 5, 0],

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

Вам наверняка пришло в голову, что вы используете очень много памяти для выполнения простой операции, которая на самом деле может быть сделана на месте. Обычно причина, по которой следует избегать выполнения операции на месте, заключается в том, что вам нужно сохранить исходный вектор, но вы вычисляете медианы с qsort который сортирует на месте, поэтому исходный вектор уже изменен. Если это приемлемо, то нет причин не использовать остальную часть алгоритма медианы медиан на месте. [1]

Кстати, хотя я, конечно, не из тех, кто боится вычислений с плавающей точкой, нет никаких оснований для countSets = ceil(float(n)/float(Q)), (n + Q - 1)/Q будет работать просто отлично. Эта идиома могла бы быть с пользой использована при вычислении size а также, хотя я не совсем уверен, где вы взяли 3n/4 вычисление в первую очередь.

---

[Примечание 1] Подсказка: вместо последовательной группировки разделите вектор на пять областей и найдите медиану i-^го элемента каждой области. Найдя его, поменяйте местами с i-^м элементом первого региона; Как только это будет сделано, ваш первый регион - первая пятая вектора - содержит медианы, и вы сможете вернуться к этому субвектору. Это означает, что на самом деле выписать медианный код в виде серии сравнений, что утомительно, но намного быстрее, чем вызов qsort, Это также позволяет избежать вырожденного случая, о котором я упоминал выше, когда вычисление медианы медиан неверно возвращает наименьший элемент в векторе.