Quicksort algorithm is Causing stack overflow [modified]
-
I do not understand why this is happening, however the following functions work for small numbers of data, but for larger numbers (ie 100,000 to 1,000,000) I get a stack overflow. These are protected functions of the class "Sample." Sample has a one dimensional dynamically allocated array of doubles pointed to by the m_data variable. Any help would be appreciated because I have not been able to find a solution to this Thanks
void Sample::quicksort(signed long int top, signed long int bottom){ signed int long middle; if (top < bottom){ middle = partition(top, bottom); quicksort(top, middle); quicksort(middle+1, bottom); } return; } signed long int Sample::partition(signed long int top, signed long int bottom){ double x = *(m_data + top); signed long int i = top - 1; signed long int j = bottom + 1; double temp; do{ do{ j--; }while (x > *(m_data+j)); do{ i++; }while (x < *(m_data+i)); if (i < j){ temp = *(m_data+i); *(m_data+i) = *(m_data+j); *(m_data+j) = temp; } }while (i < j); return j; // returns middle index }You have recursive function calls. Every time a recursive function is called, the state of the caller is pushed onto the stack so it can be popped off the stack when the called function returns in order to restore the state. You are simply running out of stack space as a result.
You may be right
I may be crazy
-- Billy Joel --Within you lies the power for good, use it!!!
-
I do not understand why this is happening, however the following functions work for small numbers of data, but for larger numbers (ie 100,000 to 1,000,000) I get a stack overflow. These are protected functions of the class "Sample." Sample has a one dimensional dynamically allocated array of doubles pointed to by the m_data variable. Any help would be appreciated because I have not been able to find a solution to this Thanks
void Sample::quicksort(signed long int top, signed long int bottom){ signed int long middle; if (top < bottom){ middle = partition(top, bottom); quicksort(top, middle); quicksort(middle+1, bottom); } return; } signed long int Sample::partition(signed long int top, signed long int bottom){ double x = *(m_data + top); signed long int i = top - 1; signed long int j = bottom + 1; double temp; do{ do{ j--; }while (x > *(m_data+j)); do{ i++; }while (x < *(m_data+i)); if (i < j){ temp = *(m_data+i); *(m_data+i) = *(m_data+j); *(m_data+j) = temp; } }while (i < j); return j; // returns middle index }Any recursive function can cause a stack overflow if it recurses too often.
JKallen wrote:
signed int long middle;
Is this legal ? It's certainly redundant. Variables are signed by default, and long and int are the same, so long would have done. Why is it there, this can't be C, it's a class. You've created a variable before it needs to exist ( and when sometimes it does not ), and not given it a default value. This is very poor form.
Christian Graus - Microsoft MVP - C++ Metal Musings - Rex and my new metal blog
-
You have recursive function calls. Every time a recursive function is called, the state of the caller is pushed onto the stack so it can be popped off the stack when the called function returns in order to restore the state. You are simply running out of stack space as a result.
You may be right
I may be crazy
-- Billy Joel --Within you lies the power for good, use it!!!
-
Any recursive function can cause a stack overflow if it recurses too often.
JKallen wrote:
signed int long middle;
Is this legal ? It's certainly redundant. Variables are signed by default, and long and int are the same, so long would have done. Why is it there, this can't be C, it's a class. You've created a variable before it needs to exist ( and when sometimes it does not ), and not given it a default value. This is very poor form.
Christian Graus - Microsoft MVP - C++ Metal Musings - Rex and my new metal blog
It is legal. It is only redundant on a per compiler basis. long signed int specifies for all compilers where some platforms may default to short as the old C++ compilers do,..etc. the definition is fine. in fact I changed the "ints" to short signed unsigned lnog etc,...no difference. The problem is that I am running out of stack,...what i dont get is why this happenes sorting 3000 items.
-
It is legal. It is only redundant on a per compiler basis. long signed int specifies for all compilers where some platforms may default to short as the old C++ compilers do,..etc. the definition is fine. in fact I changed the "ints" to short signed unsigned lnog etc,...no difference. The problem is that I am running out of stack,...what i dont get is why this happenes sorting 3000 items.
JKallen wrote:
It is only redundant on a per compiler basis.
Yes, it's true that the standard only sets minimum sizes for variable types, a long may be bigger than an int. But I don't see how 'long' wouldn't work everywhere ?
JKallen wrote:
in fact I changed the "ints" to short signed unsigned lnog etc,...no difference
I know that, I was making a general comment about the efficiency and cleanness of the code.
JKallen wrote:
The problem is that I am running out of stack,...what i dont get is why this happenes sorting 3000 items.
Obviously because each call is placing two more calls on the stack, and you're running out. What if you add a counter to the code, a static variable or something ? Perhaps the loop is running for more often than it needs to, and there's a bug in the partition code ?
Christian Graus - Microsoft MVP - C++ Metal Musings - Rex and my new metal blog
-
JKallen wrote:
It is only redundant on a per compiler basis.
Yes, it's true that the standard only sets minimum sizes for variable types, a long may be bigger than an int. But I don't see how 'long' wouldn't work everywhere ?
JKallen wrote:
in fact I changed the "ints" to short signed unsigned lnog etc,...no difference
I know that, I was making a general comment about the efficiency and cleanness of the code.
JKallen wrote:
The problem is that I am running out of stack,...what i dont get is why this happenes sorting 3000 items.
Obviously because each call is placing two more calls on the stack, and you're running out. What if you add a counter to the code, a static variable or something ? Perhaps the loop is running for more often than it needs to, and there's a bug in the partition code ?
Christian Graus - Microsoft MVP - C++ Metal Musings - Rex and my new metal blog
-
So. Is the message you cannot sort more than 3000 items using a quick sort algorithm? Is there a way around this limitation? ie is there a way to manage the recursive calls dynamically?
JKallen wrote:
Is the message you cannot sort more than 3000 items using a quick sort algorithm?
No, the message is that apparently you can't do that using this particular implimentation.
JKallen wrote:
ie is there a way to manage the recursive calls dynamically?
Not that I know of. I believe you can change your stack size, but this is a poor solution IMO.
Christian Graus - Microsoft MVP - C++ Metal Musings - Rex and my new metal blog
-
I do not understand why this is happening, however the following functions work for small numbers of data, but for larger numbers (ie 100,000 to 1,000,000) I get a stack overflow. These are protected functions of the class "Sample." Sample has a one dimensional dynamically allocated array of doubles pointed to by the m_data variable. Any help would be appreciated because I have not been able to find a solution to this Thanks
void Sample::quicksort(signed long int top, signed long int bottom){ signed int long middle; if (top < bottom){ middle = partition(top, bottom); quicksort(top, middle); quicksort(middle+1, bottom); } return; } signed long int Sample::partition(signed long int top, signed long int bottom){ double x = *(m_data + top); signed long int i = top - 1; signed long int j = bottom + 1; double temp; do{ do{ j--; }while (x > *(m_data+j)); do{ i++; }while (x < *(m_data+i)); if (i < j){ temp = *(m_data+i); *(m_data+i) = *(m_data+j); *(m_data+j) = temp; } }while (i < j); return j; // returns middle index }Have a look at this implementation. It's optimized for speed and size. http://epaperpress.com/sortsearch/txt/qui.txt[^]
-
I do not understand why this is happening, however the following functions work for small numbers of data, but for larger numbers (ie 100,000 to 1,000,000) I get a stack overflow. These are protected functions of the class "Sample." Sample has a one dimensional dynamically allocated array of doubles pointed to by the m_data variable. Any help would be appreciated because I have not been able to find a solution to this Thanks
void Sample::quicksort(signed long int top, signed long int bottom){ signed int long middle; if (top < bottom){ middle = partition(top, bottom); quicksort(top, middle); quicksort(middle+1, bottom); } return; } signed long int Sample::partition(signed long int top, signed long int bottom){ double x = *(m_data + top); signed long int i = top - 1; signed long int j = bottom + 1; double temp; do{ do{ j--; }while (x > *(m_data+j)); do{ i++; }while (x < *(m_data+i)); if (i < j){ temp = *(m_data+i); *(m_data+i) = *(m_data+j); *(m_data+j) = temp; } }while (i < j); return j; // returns middle index }I've not ever seen top/bottom used with quicksort. I use left/right. That aside... The reason for the endless recursion is that
topis always LTbottom. See if this helps:void Sample::quicksort( int top, int bottom )
{
if (top < bottom)
{
int nMiddle = partition(top, bottom);
quicksort(top, nMiddle- 1);
quicksort(nMiddle + 1, bottom);
}
}
"Money talks. When my money starts to talk, I get a bill to shut it up." - Frank
"Judge not by the eye but by the heart." - Native American Proverb
-
I do not understand why this is happening, however the following functions work for small numbers of data, but for larger numbers (ie 100,000 to 1,000,000) I get a stack overflow. These are protected functions of the class "Sample." Sample has a one dimensional dynamically allocated array of doubles pointed to by the m_data variable. Any help would be appreciated because I have not been able to find a solution to this Thanks
void Sample::quicksort(signed long int top, signed long int bottom){ signed int long middle; if (top < bottom){ middle = partition(top, bottom); quicksort(top, middle); quicksort(middle+1, bottom); } return; } signed long int Sample::partition(signed long int top, signed long int bottom){ double x = *(m_data + top); signed long int i = top - 1; signed long int j = bottom + 1; double temp; do{ do{ j--; }while (x > *(m_data+j)); do{ i++; }while (x < *(m_data+i)); if (i < j){ temp = *(m_data+i); *(m_data+i) = *(m_data+j); *(m_data+j) = temp; } }while (i < j); return j; // returns middle index }
