A strange limit for my quicksorting code
Aug 6, 2017 at 4:10pm UTC
Here is my code
The problem is when I change nNum, the size of the array,
to 520241, the thing crashes. When it is 520240, the program
(without printing all the values) runs within a second. I
changed every number in this code to long, same problem.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
#include <iostream>
#include <stdlib.h>
using namespace std;
long maxN, nNum;
bool spaceBefore;
void qSort(long unsorted[], long begCursor, long endCursor) {
if (begCursor>=endCursor) {
return ;
}
long pivot=endCursor;
long wall=begCursor, cTL=begCursor; //cTL means "check if could switch to left"
bool nothingDone;
while (wall<=pivot-(long )1&&cTL<=endCursor) {
nothingDone=true ;
if (unsorted[wall]<unsorted[pivot]) {
wall++;
nothingDone=false ;
if (cTL<=wall) {
cTL=wall+(long )1;
}
if (wall==pivot-(long )1) {
continue ;
}
continue ;
}
else if (cTL<endCursor&&unsorted[wall]>=unsorted[pivot]) {
while (cTL<endCursor) {
if (unsorted[cTL]<unsorted[pivot]) {
unsorted[cTL]=unsorted[cTL]^unsorted[wall];
unsorted[wall]=unsorted[cTL]^unsorted[wall];
unsorted[cTL]=unsorted[cTL]^unsorted[wall];
cTL++;
wall++;
nothingDone=false ;
break ;
}
cTL++;
nothingDone=false ;
}
}
if (nothingDone) {break ;}
if (cTL>=endCursor) {
break ;}
}
if ((pivot!=wall)&&(unsorted[pivot]!=unsorted[wall])) {
unsorted[pivot]=unsorted[pivot]^unsorted[wall];
unsorted[wall]=unsorted[pivot]^unsorted[wall];
unsorted[pivot]=unsorted[pivot]^unsorted[wall];}
long nextEnd=wall-(long )1;
long nextStart=wall+(long )1;
qSort(unsorted,begCursor,nextEnd);
qSort(unsorted,nextStart,endCursor);
return ;
}
int main()
{
maxN=10000000;
nNum=520241; //currently it crashes
// cin >> maxN >> nNum;
long unsorted[nNum];
for (long loop=0; loop<nNum;loop++) {
unsorted[loop]=rand()%(maxN+1);
}
qSort(unsorted,(long )0,nNum-(long )1);
/* spaceBefore=false;
for (long loop=0; loop<nNum;loop++) {
if (spaceBefore==true) {
cout << " ";
}
cout << unsorted[loop];
spaceBefore=true;
} */
return 0;
}
Last edited on Aug 6, 2017 at 4:11pm UTC
Aug 6, 2017 at 4:29pm UTC
You may be running out of stack space. Try using an array with a static storage duration.
1 2
// long unsorted[nNum]; // line 69
static long unsorted[nNum];
Topic archived. No new replies allowed.