Ошибки во время выполнения в C ++ реализации быстрой сортировки

Question

Я пишу реализацию быстрой сортировки, чтобы освежить свои навыки C ++, но столкнулся с ошибкой, которая вводит меня в заблуждение. Кажется, что алгоритм работает нормально примерно в 25% случаев, но я продолжаю сталкиваться с ошибками в остальные 75% случаев, когда программа сообщает либо об ошибке сегментации, либо о переполнении стека. Если бы кто-то мог помочь, это было бы очень ценно. Заранее спасибо.

#include <iostream>
#include <string.h>
#include <ctime>
using namespace std;

#define size 20

void printSet(int* set);
int* quicksort(int* set, int l);
int* concat(int* less, int countL, int* greater, int countG);

int main()
{
    srand(time(NULL));
    int* set;
    set = new int[size];
    for(int i=0; i<size; i++)
        set[i]=rand()%200;
    printSet(set);
    set = quicksort(set, size);
    printSet(set);
    delete set;
    int i;
    cin>> i;
    return 0;
}

int* quicksort(int* set, int l)
{
    //cout<<"QS\n";
    if (l <= 1)
        return set;
    int*      less = new int[l];
    int*   greater = new int[l];
    int pivotIndex = rand() % l, 
          pivotVal = set[pivotIndex],
            countL = 0,
            countG = 0;

    for(int i=0; i<l; i++)
    {
        if (set[i] < pivotVal)
            less[countL++]=set[i];
        else
            greater[countG++]=set[i];
    }
    set = concat(quicksort(less, countL), countL, quicksort(greater, countG), countG);

    return set;
}

int* concat(int* less, int countL, int* greater, int countG)
{
    //cout<<"concat\n";
    int* set;
    set = new int[size];

    int i;

    for(i=0; i<countL; i++)
        set[i]=less[i];
    for(int j=0; j<countG; j++)
        set[i+j]=greater[j];

    return set;
}

void printSet(int* set)
{
    cout<<"******************\nPrinting Set\n";
    for(int i=0; i< size; i++)
    {
        cout<<i<<": "<<set[i]<<endl;
    }
}

Answer 1

Я считаю, что одна из ваших ошибок в этой строке в основном:

delete set;

Проблема в том, что set - это массив, выделенный с new[]. Чтобы освободить его память, вам нужно удалить его с соответствующим вызовом на delete[]. Это можно исправить, переписав строку как

delete[] set;

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

for(int i=0; i<l; i++)
{
    if (set[i] < pivotVal)
        less[countL++]=set[i];
    else
        greater[countG++]=set[i];
}
set = concat(quicksort(less, countL), countL, quicksort(greater, countG), countG);

Поскольку ваш элемент pivot равен 0 (это единственный выбор!), Вы будете перебирать массив и помещать оба 0 в массиве в greater. Следовательно, когда вы рекурсивно вызываете quicksort на greater, вы в конечном итоге рекурсивно пытаетесь отсортировать тот же самый диапазон, с которого вы начали, что приводит к бесконечной рекурсии.

Чтобы исправить это, попробуйте обновить код, чтобы разделить его на три группы: элементы меньше, чем точка, элементы больше, чем точка, и элементы, равные точке. Вы все равно будете использовать меньшие и большие диапазоны, но не будете рекурсивно вызывать себя на равных значениях. Это гарантирует, что рекурсия всегда вызывается на меньших диапазонах, чем вы начали.

Наконец, как уже отмечали другие, ваша текущая реализация теряет много памяти, потому что вы никогда не освобождаете ни один из создаваемых вами временных массивов. Чтобы избежать этого, подумайте о том, чтобы заменить использование необработанных массивов на std::vector, который выполняет свое собственное управление памятью и не теряет какую-либо память. Кроме того, это значительно упрощает разбиение массива на регионы, поскольку вы можете просто использовать push_back для добавления элементов.

Надеюсь, это поможет!