int a[1000000]; //can't compile!

[I am learning]

My short program( quicksort)
/////////////////

include "iostream"

include "time.h"

define nx 1000000

using namespace std;
void qsort(int array[],long first,long last)
{
long lb=first,ub=last;
int pivot=array[(first+last)/2];
int temp;
do
{
while(array[lb]<pivot) lb++;
while(array[ub]>pivot) ub--;
if(lb<=ub)
{
temp=array[lb];
array[lb]=array[ub];
array[ub]=temp;
lb++;
ub--;
}
}
while(lb<=ub);
if(first<ub) qsort(array,first,ub);
if(last>lb) qsort(array,lb,last);
}
int main()
{
int a[nx];
unsigned long start, end,i,n=nx;
start=clock();
srand((unsigned)time(0));
for(i=0;i<n;i++)
a[i]=(rand()%10000+1);
qsort(a,0,n);
end=clock();
cout<<endl<<end-start;
//for(i=0;i<n;i++)
//cout<<a[i]<<endl;
system("PAUSE");
}

////////
if you reduce nx to 100000, then this program will work in 16mili (s) (it depend on your CPU, ram...)
but why it can not compile with nx=1000000( 1M)? how to solve it? or can we solve it?
thanks!

[I am learning]

qsort(a,0,nx-1); : oh my god, that's my problem! I often got stupid mistake like that. thanks

[Wayne Keen]

Do you understand the difference between stack and heap?

You are trying to declare a huge array in a very limited resource.

Large arrays will need to be set up in heap, through the "new" command.

Does this ring any bells, or is this new ground for you?

Wayne

[cpns]

Are you sure that it failed to compile? It should have compiled. However it would have crashed when you ran it - is that what you really meant?

If it did fail to compile you should post the log (but I doubt that it did).

Any way, local non-static variables are created on the stack, which in Windows is typically about 2Mb per thread.

The quick-and-dirty fix in this case is:

static int a[nx];

However, that is not to say that that is a good solution in all circumstances. In cases where the memory is only needed briefly rather than for the duration of the execution, it is more efficient to use dynamic memory allocation. In C++ that is best done with the new[] and delete[] operators:

int* a = new int[nx] ;

// use a...

delete [] a ;

Clifford

[I am learning]

Yes, I'm sorry, I can compile this program, but when run, it crash.
@Wayne Keen: Yes, I just study basic C++ ( with Turbo C++ 3.0) at University for 1 semester...

@cpns: Yes, thanks! I modify as you wrote, and my program can run with nx=1M or lager. But it can not run with nx=100k!( but can run with nx=10k or smaller!)
Can you tell me why? Thanks!

[cpns]

>nx=100k

As well as the 2Mb (or thereabouts) limit for the stack, there is a 2Gb total memory limit per process (dynamic, static, or otherwise). However int a[1000000] is less than 4Mb, so it should be fine. If you have modified the code you need to post the new code - even if you think you did exactly as asked.

Besides you said "I modify as you wrote...", but I suggested two solutions, so that does not really help.

Clifford

[I am learning]

my new code( work with nx=1M, not with 100k)
( I use
int* a = new int[nx] ;

// use a...

delete [] a ;

)
//////////////////

include "iostream"

include "time.h"

define nx 1000000

using namespace std;
void qsort(int array[],long first,long last)
{
long lb=first,ub=last;
int pivot=array[(first+last)/2];
int temp;
do
{
while(array[lb]<pivot) lb++;
while(array[ub]>pivot) ub--;
if(lb<=ub)
{
temp=array[lb];
array[lb]=array[ub];
array[ub]=temp;
lb++;
ub--;
}
}
while(lb<=ub);
if(first<ub) qsort(array,first,ub);
if(last>lb) qsort(array,lb,last);
}
int main()
{
int* a= new int[nx];
//int a[nx]; // this work with 100k
unsigned long start, end,i,n=nx;
start=clock();
srand((unsigned)time(0));
for(i=0;i<n;i++)
a[i]=(rand()%10000+1);
//for(i=0;i<1000;i++) // test how long does it take if quick sort 1000 times
qsort(a,0,n);
delete [] a;
end=clock();
cout<<endl<<end-start<<endl;
//for(i=0;i<n;i++)
// cout<<a[i]<<endl;

system("PAUSE");

}

////////
thank 4 helping me

[Wayne Keen]

Please don't make this a magic word sort of solution.

If you really understand what the stack and heap are, and realize that you were declaring a huge array on the stack, then the fact that it crashes at runtime should be no surprise.

Please make sure that you understand the reasons.

Wayne

[cpns]

If it works for you at 1M, it is probably more luck than judgement. I ran it in VC++ and it generated an exception. This is probably the same problem you are seeing at 100K.

You are making an out-of-bounds array access because n = nx, but the last element of the array is a[nx-1].

What is the purpose of the variable 'n' in any case, you set it equal to nx, but never then modify it. Why not use nx directly?

int main()
{
int* a= new int[nx];
unsigned long start, end,i;
start=clock();
srand((unsigned)time(0));
for(i=0;i<nx;i++)
{
a[i]=(rand()%10000+1);
}
qsort(a,0,nx-1);
delete [] a;
end=clock();
cout<<endl<<end-start<<endl;

system("PAUSE");

}

A few other points.

1) Use <...> for standard headers not "...", e.g:

include <iostream>

2) Do not call your sort function qsort() since that is already the name of a function in the standard library.

3) The expression a[i]=(rand()%10000+1); will result in a far less than random distribution. There is a modulo-bias for any range that is not a factor of RAND_MAX+1, and that bias is significant is the range is a large proportion of RAND_MAX. See http://www.azillionmonkeys.com/qed/random.html.

Clifford

[cpns]

Note: The out-of-bounds access corrupted the heap, so that the exception ocurred a the delete[]. There is no substitute for using a debugger effectively.

Clifford