CODEWITHSUNDEEP
c++sortingquicksort
user9111757
user9111757

Reputation:

C++ run time error with quick sort algorithm throwing stack dump error

The code works fine when I try size = 20000 and it seems to fail when I try size = 50000 giving me the following error:

2 [] cppapplication_4 7628 cygwin_exception::open_stackdumpfile: Dumping stack trace to cppapplication_4.exe.stackdump

long long compares; // for counting compares
long long swaps; // for counting swaps
bool counted_less(int n1, int n2) {
    ++compares;
    return n1 < n2;
}

void counted_swap(int& n1, int& n2) {
    ++swaps;
    int t = n1;
    n1 = n2;
    n2 = t;
}

int* partition(int* start, int* stop) {
    int noUse=99;
    int* pivot = (stop - 1); // you can randomly pick one as the pivot
    int* i = start;
    int* j = stop - 1;
    for (;;) {
        while (*i < *pivot && i < stop)
        {
            counted_less(noUse,noUse);
            counted_less(noUse,noUse);
            ++i;
        }
            counted_less(noUse,noUse);
            counted_less(noUse,noUse);
        // skip "low" on left side
        while (*j >= *pivot && j > start) {
            counted_less(noUse,noUse);
            counted_less(noUse,noUse);
            --j;
        }
            counted_less(noUse,noUse);
            counted_less(noUse,noUse);

        // skip "high" on right side
        if (i >= j) 
        {
            counted_less(noUse,noUse);
            break;
        }
        else
        {
            counted_less(noUse,noUse);
        }
        swap(*i, *j);
        counted_swap(noUse,noUse);// swap out-of-place items
    }
    swap(*(stop - 1), *i); 
    counted_swap(noUse,noUse);// swap pivot to the final place i
    return i;

}
void quickSort(int* start, int* stop) {
    int noUse=99;
    if (start>= stop){
        counted_less(noUse,noUse);
        return;
    }
    else
    {
        counted_less(noUse,noUse);
    }
    int* pivot = partition(start,stop);
    quickSort(start, pivot);
    quickSort((pivot +1), stop);
}

int main()
{
    int size = 20000;
    int* data = new int[size];
     for (int i = 0; i < size; ++i) data[i] = i;
     quickSort(data, data + size);
}

I think the error means that I am going over a data type storage limit, I think the problem was with me using int so I changed all the int to long long and that still didn't fix it. And by the logic of the code I don't think that we are changing the size of an array. So I am not sure what caused the error.

Upvotes: 1

Views: 190

Answers (1)

rustyx
rustyx

Reputation: 85256

You're probably getting a stack overflow. That's why recursion is bad.

As a temporary workaround try increasing the stack size by linking with --stack 16777216:

$ g++ -Wl,--stack,16777216  . . .

== EDIT ==

Also your choice of pivot at (end - 1) is not good. Try setting the pivot in the middle.

    int* pivot = (stop - start)/sizeof(int*)/2 + start;

Upvotes: 1

Related Questions