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

Question

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.

Operator new can throw std::bad_alloc, check if it is not an issue in your case. Also you can compile your program without optimization, with debug symbols and investigate stack trace - it will point where your program crashed. — pptaszni
– pptaszni, Commented Oct 8, 2018 at 8:42
Were you provided with counted_less? It seems strange that you are calling it with garbage and ignoring it's return value every time — Caleth
– Caleth, Commented Oct 8, 2018 at 8:42
I would expect it to be used like if (!counted_less(start, stop)) return; and while(counted_less(*i, *pivot) && counted_less(*i, stop)) ++i; — Caleth
– Caleth, Commented Oct 8, 2018 at 8:45
@Caleth yea that is how I was suppose to do it, but I was lazy and did it that way instead — user9111757
– user9111757, Commented Oct 8, 2018 at 8:53
@glockm15 If I were marking this assignment, you'd get 0 for that — Caleth
– Caleth, Commented Oct 8, 2018 at 8:55

rustyx · Accepted Answer · 2018-10-08 09:14:32Z

1

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;

edited Oct 8, 2018 at 9:14

answered Oct 8, 2018 at 9:02

rustyx

86.4k28 gold badges224 silver badges298 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Caleth Over a year ago

Looks like this. When I ran it and printed the counts it looks like we are in the pathological bad pivot case

user9111757 Over a year ago

Sorry I am not very good at this programming stuff, where do I use that code to increase stack size?

rustyx Over a year ago

That depends on how you run compile and run your code. What tool do you use for that?

user9111757 Over a year ago

Just the netbeans

rustyx Over a year ago

Application stack size has a limit, it's not related to your PC memory, but is much less. On Windows the default is 1 MB. You can increase it if you need more stack, that's what that linker option does.

|

Collectives™ on Stack Overflow

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

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related