a rand array

[RoSsIaCrIiLoIA]

Write a function that gets an array of unsigned int
fill it with random values all differents,
and sorts it. It should be faster than qsort too.

Do you like my solution?
_______________________

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void
ArrRand(unsigned* a, unsiged size, unsigned superiore)
{static int m = 1;
unsigned i, j, h, temp;

if(a==0 || size<2 || superiore==0)
return;
if(m)
{ m = 0; srand(time(0));}
for( i = 0; i < size; ++i)
{label:
a[i] = _lrand() % superiore; /*_lrand is for Borland */
for( j = 0; j < i; ++j) /* if not, use your_lrand() */
{if(a[i] == a[j]) goto label;
else if(a[i] < a[j]) /* that fill an unsigned */
{temp = a[i];
for( h = i; h > j; --h)
a[h] = a[h - 1];
a[j] = temp;
break;
}
}
}
}

/* it is a c++ main */
int main(void)
{unsigned a[100] = {0}, i;

ArrRand( a, (sizeof a)/(sizeof *a), 80000000);
for( i = 0; i < 99; ++i)
cout << " " << a[i];
cout << "\n";
return 0;
}

[RoSsIaCrIiLoIA]

On Fri, 21 May 2004 06:07:59 GMT, RoSsIaCrIiLoIA <[e-mail]> wrote:

Write a function that gets an array of unsigned int
fill it with random values all differents,
and sorts it. It should be faster than qsort too.

Do you like my solution?
_______________________

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void
ArrRand(unsigned* a, unsiged size, unsigned superiore)
{static int m = 1;
unsigned i, j, h, temp;

if(a==0 || size<2 || superiore==0)
return;
if(m)
{ m = 0; srand(time(0));}
for( i = 0; i < size; ++i)
{label:
a[i] = _lrand() % superiore; /*_lrand is for Borland */

a[i] = (unsigned) _lrand() % superiore;

[josh]

RoSsIaCrIiLoIA wrote:

Write a function that gets an array of unsigned int
fill it with random values all differents,
and sorts it. It should be faster than qsort too.

Do you like my solution?
Aside from the fact that this code doesn't compile, you'll never beat
qsort with this method except maybe with tiny arrays.

In particular, inserting an element into an arbitrary position in an
array is O(N). Since you do this for each element, your algorithm will
have time complexity of at least O(N^2).

If you filled an array with random values and then passed that to qsort,
you'd get O(NlogN). For sufficiently large values of N, this will beat
O(N^2) nearly every time.

It should be possible to get a sorted array of random distinct integers
in time O(N), but not by choosing random numbers and sorting. (which
the problem description seems to require)
_______________________

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void
ArrRand(unsigned* a, unsiged size, unsigned superiore) ^^^^^^^
No such thing as unsiged.
{static int m = 1;
unsigned i, j, h, temp;

if(a==0 || size<2 || superiore==0)
return;
if(m)
{ m = 0; srand(time(0));}
for( i = 0; i < size; ++i)
{label:
a[i] = _lrand() % superiore; /*_lrand is for Borland */
for( j = 0; j < i; ++j) /* if not, use your_lrand() */
{if(a[i] == a[j]) goto label;
Infinite loop if superiore < size. (wouldn't be fatal if it were
documented)

If you split the insertion into a separate function you could eliminate
the goto and make the code more clear. But as I said above, inserting
like this is probably not what you want to do anyway.
else if(a[i] < a[j]) /* that fill an unsigned */
Linear search isn't all that great, but it doesn't matter much in this case.
{temp = a[i];
for( h = i; h > j; --h)
a[h] = a[h - 1];
This takes O(N) to insert an element and is repeated N times, making
your algorithm O(N^2). (The linear search does too, but that takes less
modification to fix.)
a[j] = temp;
break;
}
}
}
}

/* it is a c++ main */
int main(void)
{unsigned a[100] = {0}, i;

ArrRand( a, (sizeof a)/(sizeof *a), 80000000);
for( i = 0; i < 99; ++i)
cout << " " << a[i];
cout << "\n";
What about poor neglected a[99]?
return 0;
}

-josh

[Allan Bruce]

"RoSsIaCrIiLoIA" <[e-mail]> wrote in message
news:1v********************************@4ax.com...

Write a function that gets an array of unsigned int
fill it with random values all differents,
and sorts it. It should be faster than qsort too.

Do you like my solution?

a much faster solution would be something like this (untested):
#include <time.h>

#define NUM_ELEMENTS 100

int main(void)
{
unsigned array[NUM_ELEMENTS];
unsigned value;
int loop;

srand(time(NULL));

value = (unsigned)rand()/(RAND_MAX/NUM_ELEMENTS);

for (loop=1; loop<NUM_ELEMENTS; loop++)
{
array[loop] = value;
value += (unsigned)rand()/(RAND_MAX/NUM_ELEMENTS);
}

return 0;
}
Now there are (severe) problems with this method, i.e. you cant tell the
range of the numbers precisely, but since you didn't specify that, then this
meets your problem.
Allan

[RoSsIaCrIiLoIA]

On Fri, 21 May 2004, josh wrote:

In particular, inserting an element into an arbitrary position in an
array is O(N). Since you do this for each element, your algorithm will
have time complexity of at least O(N^2).
So you can do it in O(NlogN + N + D*N)?
If you use qsort will be O(NlogN) if you
label:
check for equals in array is O(N)
and rand() and goto label until no equal
If you filled an array with random values and then passed that to qsort,
you'd get O(NlogN). For sufficiently large values of N, this will beat
O(N^2) nearly every time.
seems to me I take O(N*N/2)
It should be possible to get a sorted array of random distinct integers
in time O(N),
How?

#include <stdio.h>
#include <iostream.h> #include <stdlib.h>
#include <time.h>

void
ArrRand(unsigned* a, unsiged size, unsigned superiore)

^^^^^^^
No such thing as unsiged.

unsigned

{static int m = 1;
unsigned i, j, h, temp;

if(a==0 || size<2 || superiore==0)
return;
if(m)
{ m = 0; srand(time(0));}
for( i = 0; i < size; ++i)
{label:
a[i] = _lrand() % superiore; /*_lrand is for Borland */
for( j = 0; j < i; ++j) /* if not, use your_lrand() */
{if(a[i] == a[j]) goto label;

Infinite loop if superiore < size. (wouldn't be fatal if it were
documented)

balle
If you split the insertion into a separate function you could eliminate
the goto and make the code more clear. But as I said above, inserting
like this is probably not what you want to do anyway.

else if(a[i] < a[j]) /* that fill an unsigned */

Linear search isn't all that great, but it doesn't matter much in this case.

{temp = a[i];
for( h = i; h > j; --h)
a[h] = a[h - 1];

This takes O(N) to insert an element and is repeated N times, making
your algorithm O(N^2). (The linear search does too, but that takes less
modification to fix.)

I search O(pos) and pos E [0, N) and not O(N^2)

[...]

ArrRand( a, (sizeof a)/(sizeof *a), 80000000);
for( i = 0; i < 99; ++i)
cout << " " << a[i];
cout << "\n";

What about poor neglected a[99]?

I forgot it

[Mark A. Odell]

RoSsIaCrIiLoIA <[e-mail]> wrote in
news:5g********************************@4ax.com:

#include <iostream.h>

This is a C++ include file, not C, which is what we discuss here.

--
- Mark ->
--

[Martin Ambuhl]

Mark A. Odell wrote:

RoSsIaCrIiLoIA <[e-mail]> wrote in
news:5g********************************@4ax.com:

#include <iostream.h>

This is a C++ include file, not C, which is what we discuss here.

You're right that it's not a C header, but you're wrong in that it is
neither C++ nor an "include file."

[Mark A. Odell]

Martin Ambuhl <ma*****@earthlink.net> wrote in
news:2h************@uni-berlin.de:

#include <iostream.h>

This is a C++ include file, not C, which is what we discuss here.

You're right that it's not a C header, but you're wrong in that it is
neither C++ nor an "include file."

I thought it was a C++ header file.

--
- Mark ->
--

[red floyd]

"Allan Bruce" <al*****@TAKEAWAYf2s.com> wrote in message news:<c8**********@news.freedom2surf.net>...

"RoSsIaCrIiLoIA" <[e-mail]> wrote in message
news:1v********************************@4ax.com...

Write a function that gets an array of unsigned int
fill it with random values all differents,
and sorts it. It should be faster than qsort too.

Do you like my solution?

a much faster solution would be something like this (untested):
#include <time.h>

#define NUM_ELEMENTS 100

int main(void)
{
unsigned array[NUM_ELEMENTS];
unsigned value;
int loop;

srand(time(NULL));

value = (unsigned)rand()/(RAND_MAX/NUM_ELEMENTS);

for (loop=1; loop<NUM_ELEMENTS; loop++)
{
array[loop] = value;
value += (unsigned)rand()/(RAND_MAX/NUM_ELEMENTS);
}

return 0;
}

Unsorted and you don't fill array[0].

But the OP's question is bogus, because on random data, Quicksort is
the fastest general algorithm. He might do better with a heapsort,
simply because while it's got a higher coefficent, it's still O(n log
n), in *ALL* cases, whereas Quicksort is O(n^2) in the worst case.

[Martin Ambuhl]

Mark A. Odell wrote:

Martin Ambuhl <ma*****@earthlink.net> wrote in
news:2h************@uni-berlin.de:

#include <iostream.h>

This is a C++ include file, not C, which is what we discuss here.

You're right that it's not a C header, but you're wrong in that it is
neither C++ nor an "include file."

I thought it was a C++ header file.

The C++ header (not "header file") is named <iostream>

[Mark A. Odell]

Martin Ambuhl <ma*****@earthlink.net> wrote in
news:2h************@uni-berlin.de:

>#include <iostream.h>

This is a C++ include file, not C, which is what we discuss here.

You're right that it's not a C header, but you're wrong in that it is
neither C++ nor an "include file."

I thought it was a C++ header file.

The C++ header (not "header file") is named <iostream>

How weird! One more reason for me to stick with C.

--
- Mark ->
--

[Alex Monjushko]

Mark A. Odell <od*******@hotmail.com> wrote:

Martin Ambuhl <ma*****@earthlink.net> wrote in
news:2h************@uni-berlin.de:

>>#include <iostream.h>

>This is a C++ include file, not C, which is what we discuss here.

You're right that it's not a C header, but you're wrong in that it is
neither C++ nor an "include file."
I thought it was a C++ header file.

The C++ header (not "header file") is named <iostream>

How weird! One more reason for me to stick with C.

If you think that this is a valid reason to be sticking with C then
I don't think that C is for you :-)

--
Alex Monjushko (mo*******@hotmail.com)

[Mark A. Odell]

Alex Monjushko<mo*******@hotmail.com> wrote in
news:2h************@uni-berlin.de:

>>>#include <iostream.h>
>
>>This is a C++ include file, not C, which is what we discuss here.
>
>You're right that it's not a C header, but you're wrong in that it is
>neither C++ nor an "include file."
I thought it was a C++ header file.

The C++ header (not "header file") is named <iostream>

How weird! One more reason for me to stick with C.

If you think that this is a valid reason to be sticking with C then
I don't think that C is for you :-)

Okay, maybe 14 years of C programming experience vs. zero for C++ is the
real reason but I still think it's weird.

--
- Mark ->
--

[Keith Thompson]

RoSsIaCrIiLoIA <[e-mail]> writes:

Write a function that gets an array of unsigned int
fill it with random values all differents,
and sorts it. It should be faster than qsort too.

Do you like my solution?

No. It doesn't compile; if you're going to post code here, take the
time to cut-and-paste the actual code that you've compiled and
executed. The main program is gratuitously written in a different
language which is off-topic in this newsgroup. The sorting algorithm
appears to be Bubblesort or something similar; you might save some
time for small arrays by avoiding the overhead of qsort(), but it's
going to be extraordinarily inefficient for large arrays. It uses a
non-standard function called "_lrand()" without indicating what it is,
or how it differs from the standard "rand()". It assumes that the
value 80000000 will fit in an unsigned int.

It's not worth my time to figure out what else might be wrong with it.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Default User]

"Mark A. Odell" wrote:

Martin Ambuhl <ma*****@earthlink.net> wrote in
news:2h************@uni-berlin.de:

>>#include <iostream.h>

>This is a C++ include file, not C, which is what we discuss here.

You're right that it's not a C header, but you're wrong in that it is
neither C++ nor an "include file."
I thought it was a C++ header file.

The C++ header (not "header file") is named <iostream>

How weird! One more reason for me to stick with C.

comp.lang.c++ has been having a discussion about the lack of extensions
on the C++ standard includes. P. J. Plaugher apparently was not a happy
camper about that decision by the committee.

Obviously not topical here, but an interesting read if you want to
wander over there.


Brian Rodenborn

[Default User]

Keith Thompson wrote:

No. It doesn't compile; if you're going to post code here, take the
time to cut-and-paste the actual code that you've compiled and
executed.

This goof is a troll, I kill-filed him long ago. I suggest all do the
same.


Brian Rodenborn

[josh]

RoSsIaCrIiLoIA wrote:

On Fri, 21 May 2004, josh wrote:

In particular, inserting an element into an arbitrary position in an
array is O(N). Since you do this for each element, your algorithm will
have time complexity of at least O(N^2).

So you can do it in O(NlogN + N + D*N)?
If you use qsort will be O(NlogN) if you
label:
check for equals in array is O(N)
and rand() and goto label until no equal

When an algorithm has a time complexity of O(f(N)), it means that there
is some k such that the time will be at most k*f(N) when N becomes
large. When N is large, NlogN dominates over N and D*N, so O(NlogN + N
+ D*N) is O(NlogN).

If you filled an array with random values and then passed that to qsort,
you'd get O(NlogN). For sufficiently large values of N, this will beat
O(N^2) nearly every time.

seems to me I take O(N*N/2)

O(N*N/2) is O(N^2) because it only differs by a constant factor. (the k
above swallows the /2)

It should be possible to get a sorted array of random distinct integers
in time O(N),

How?

lower_bound = minimum;
upper_bound = maximum - number_of_slots;
for (index=0; index<number_of_slots; ++index)
{
a[index] = random_in_range(lower_bound, upper_bound);
lower_bound = a[index]+1;
++upper_bound;
}

where random_in_range returns a random integer between lower_bound and
upper_bound, inclusive.

I don't know if the distribution would be the same with this method though.

{temp = a[i];
for( h = i; h > j; --h)
a[h] = a[h - 1];

This takes O(N) to insert an element and is repeated N times, making
your algorithm O(N^2). (The linear search does too, but that takes less
modification to fix.)

I search O(pos) and pos E [0, N) and not O(N^2)

Insertion is O(N) (I think it'll take something like N/4 iterations on
average here, not sure exactly.) and it is inside another loop with N
iterations. The linear search is also O(N), taking N/2 iterations on
average, and still inside that outer loop.

-josh

[Default User]

Default User wrote:

Keith Thompson wrote:

No. It doesn't compile; if you're going to post code here, take the
time to cut-and-paste the actual code that you've compiled and
executed.

This goof is a troll, I kill-filed him long ago. I suggest all do the
same.

Naturally I meant RoSsIaCrIiLoIA, not Keith.

Brian Rodenborn

[E. Robert Tisdale]

Default User wrote:

Default User wrote:

Keith Thompson wrote:

No. It doesn't compile; if you're going to post code here, take the
time to cut-and-paste the actual code that you've compiled and
executed.
This goof is a troll, I kill-filed him long ago.
I suggest all do the same.

Naturally I meant RoSsIaCrIiLoIA, not Keith.

Naturally.
Brian Rodenborn

Brian,

I use Mozilla to read news.
I can kill threads
but I don't know how to kill individual subscribers.
Can you tell me how to do this with Mozilla?
How would I killfile "Default User" for example?
Or do I need to get a different newsreader?
What newsreader are you using?
And what did you do to killfile "RoSsIaCrIiLoIA"?

[Default User]

"E. Robert Tisdale" wrote:

I use Mozilla to read news.
I can kill threads
but I don't know how to kill individual subscribers.
Can you tell me how to do this with Mozilla?
How would I killfile "Default User" for example?
Or do I need to get a different newsreader?
What newsreader are you using?
And what did you do to killfile "RoSsIaCrIiLoIA"?

I don't use Mozilla for news, but Netscape is very similar so it may be
the same process.

To set up a filter, I select Edit->Message Filters, then click New.
There's a pulldown menu, the default is Subject, I changed that to
Sender. Then in the box next to contains, I put in an identifying string
from the sender line (check message headers).

HTH, you hump.

Brian Rodenborn

[August Derleth]

On Fri, 21 May 2004 17:58:42 +0000, Mark A. Odell wrote:

Okay, maybe 14 years of C programming experience vs. zero for C++ is the
real reason but I still think it's weird.

I think most C programmers can pick up a C++ subset fairly easily, if they
have a good book. "Thinking in C++ 2nd Edition" by Bruce Eckel is, in my
view, one such book. It's available free online (although you need to
download the compressed (.zip) archive, and it's not browsable online).

http://www.mindview.net/Books/TICPP/...ngInCPP2e.html

(C++ subsets well, in my opinion. You can approach it from a purely non-OO
view and leverage its typechecking, Standard Template Library, and great,
standardized package of pre-defined algorithms. Eckel calls this the
"Better C" aspect of C++, but you don't need to agree. ;-) Or, if you do
want OO, you don't need to use overloading or multiple inheritance.)

--
yvoregnevna gjragl-guerr gjb-gubhfnaq guerr ng lnubb qbg pbz
To email me, rot13 and convert spelled-out numbers to numeric form.
"Makes hackers smile" makes hackers smile.

[James Kanze]

August Derleth <se*@sig.now> writes:

|> On Fri, 21 May 2004 17:58:42 +0000, Mark A. Odell wrote:

|> > Okay, maybe 14 years of C programming experience vs. zero for C++
|> > is the real reason but I still think it's weird.

|> I think most C programmers can pick up a C++ subset fairly easily,
|> if they have a good book.

I think that most good C programmers are already writing a C++ subset.
The actual incompatibilities in the common subset are fairly minor, and
most of C90 is in the common subset.

--
James Kanze
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France [phone]

[Sam Dennis]

James Kanze wrote:

I think that most good C programmers are already writing a C++ subset.

So, for example, most good C programmers cast the return value of malloc
and friends, do they?

Good C programmers know enough not to care that their code won't compile
(or will function differently) when given to a C++ compiler. It is also
possible to write C programs that function identically if taken as other
languages that are much more distantly related to C than C++, but no-one
is suggesting that writing for, say, FORTRAN compatibility (this one may
not be possible, but that's not the point) is a good practice.

....I am having a little trouble finding an example of this in a language
other than C++ for completely portable C but I can say with considerable
confidence that it should be possible with Befunge for many tasks.

--
++acr@,ka"

[RoSsIaCrIiLoIA]

On Fri, 21 May 2004 11:24:39 GMT, RoSsIaCrIiLoIA <[e-mail]> wrote:

How?

#include <stdio.h>
#include <iostream.h> #include <stdlib.h>
#include <time.h>

void
ArrRand(unsigned* a, unsiged size, unsigned superiore) ^^^^^^^
No such thing as unsiged.

unsigned

{static int m = 1;
unsigned i, j, h, temp;

if(a==0 || size<2 || superiore==0)
return; if( a==0 || size<2 || superiore<=size)
return; if(m)
{ m = 0; srand(time(0));}
for( i = 0; i < size; ++i)
{label:
a[i] = _lrand() % superiore; /*_lrand is for Borland */
for( j = 0; j < i; ++j) /* if not, use your_lrand() */
{if(a[i] == a[j]) goto label;

Infinite loop if superiore < size. (wouldn't be fatal if it were
documented)
Yes I have seen it
balle

this is syntax error
If you split the insertion into a separate function you could eliminate
the goto and make the code more clear.

It is very clear in this way too
Thank to everyone

[RoSsIaCrIiLoIA]

On Fri, 21 May 2004 20:05:20 GMT, josh
<sm*************************@yahoo.com.NOSPAM> wrote:

RoSsIaCrIiLoIA wrote:

On Fri, 21 May 2004, josh wrote:

seems to me I take O(N*N/2)
O(N*N/2) is O(N^2) because it only differs by a constant factor. (the k
above swallows the /2)
It should be possible to get a sorted array of random distinct integers
in time O(N),

How?

lower_bound = minimum;
upper_bound = maximum - number_of_slots;
for (index=0; index<number_of_slots; ++index)
{
a[index] = random_in_range(lower_bound, upper_bound);
lower_bound = a[index]+1;
++upper_bound;
}

I don't understand, but that seems to me like this

void
ordinator( unsigned* a, unsigned size, unsigned sup_val)
{static int i = 1;
unsigned j, k, h;
/*---------------------*/
if( a==0 || size<2 || sup_val<=size )
return;
if(i)
{i = 0; srand(time(0));}
h = sup_val/size;
for( j = 0; j<size; ++j)
a[j] = j*h + (unsigned) _lrand() % h;
}

or if one has a massive use of array 'a' it is possible
1) write an ordered array 'a' with an algorithm O(N^2)
label:
2) use the partition in 'a' to build a new array 'a' [O(N)]
goto label;
where random_in_range returns a random integer between lower_bound and
upper_bound, inclusive. I don't know if the distribution would be the same with this method though.

[RoSsIaCrIiLoIA]

On Fri, 21 May 2004, Keith Thompson <ks***@mib.org> wrote:

RoSsIaCrIiLoIA <[e-mail]> writes:

Write a function that gets an array of unsigned int
fill it with random values all differents,
and sorts it. It should be faster than qsort too.

Do you like my solution?

No. It doesn't compile; if you're going to post code here, take the
time to cut-and-paste the actual code that you've compiled and
executed. The main program is gratuitously written in a different
language which is off-topic in this newsgroup. The sorting algorithm
appears to be Bubblesort or something similar; you might save some
time for small arrays by avoiding the overhead of qsort(), but it's
going to be extraordinarily inefficient for large arrays. It uses a
non-standard function called "_lrand()" without indicating what it is,
or how it differs from the standard "rand()". It assumes that the
value 80000000 will fit in an unsigned int.

It's not worth my time to figure out what else might be wrong with it.

I don't say it is perfect ;)

[josh]

RoSsIaCrIiLoIA wrote:

On Fri, 21 May 2004 20:05:20 GMT, josh
<sm*************************@yahoo.com.NOSPAM> wrote:

It should be possible to get a sorted array of random distinct integers
in time O(N),

How?
lower_bound = minimum;
upper_bound = maximum - number_of_slots;
for (index=0; index<number_of_slots; ++index)
{
a[index] = random_in_range(lower_bound, upper_bound);
lower_bound = a[index]+1;
++upper_bound;
}

I don't understand, but that seems to me like this

The requirement for a sorted array is that a[i] is greater than a[i-1]
and less than a[i+1]. In addition, you are requiring that all of these
numbers be in [0, sup_val). (or in [minimum, maximum) above)

When you fill in a[0], there are no other numbers in the array to
constrain it, so you can choose any number in [0, sup_val). Except this
isn't true: if you select sup_val-1, there is no number you can pick for
a[1] that is greater than sup_val-1 and still in [0, sup_val). In an
array of N integers, there will be N-1 that need to be greater than
a[0], so a[0] must be in [0, sup_val-(N-1)). With integers we can
simplify this to [0, sup_val-N], including the upper bound.

So a[0] must be chosen in [0, sup_val-N]

Next we choose a[1], which must be greater than a[0] and still leave
room for all the rest of the array. Since there are 1 fewer integers
above a[0] than above a[1], we can just bump the upper bound by 1.

So a[1] must be chosen in [a[0]+1, sup_val-N+1]

We then continue at each step by taking the previous value as a lower
bound and increasing the upper bound by 1:

a[2] must be in [a[1]+1, sup_val-N+2]
a[3] must be in [a[2]+1, sup_val-N+3]
a[4] must be in [a[3]+1, sup_val-N+4]
....
a[N-2] must be in [a[N-3]+1, sup_val-2]
a[N-1] must be in [a[N-2]+1, sup_val-1]
(and of course there is no a[N])

So in general, a[i] must be chosen in [a[i-1]+1, sup_val-N+i]:

a[o] = random_in_range(0, sup_val-N);
for (i=1; i<N; ++i)
a[i] = random_in_range(a[i-1]+1, sup_val-N+i);

and the code above should do exactly the same thing.
void
ordinator( unsigned* a, unsigned size, unsigned sup_val)
{static int i = 1;
unsigned j, k, h;
/*---------------------*/
if( a==0 || size<2 || sup_val<=size )
return;
if(i)
{i = 0; srand(time(0));}
h = sup_val/size;
for( j = 0; j<size; ++j)
a[j] = j*h + (unsigned) _lrand() % h;
}
Not quite, this doesn't allow a[0] its full range. (or any of them
really) There are some sequences that a "generate random numbers and
sort" agorithm could generate that this algorithm cannot. Mine can
generate all of them, although I suspect the probability distribution
may be different.
or if one has a massive use of array 'a' it is possible
1) write an ordered array 'a' with an algorithm O(N^2)
label:
2) use the partition in 'a' to build a new array 'a' [O(N)]
goto label;

Not sure what you mean here... (sounds like it'd still be at least O(N^2)?)

If you have room for M bits (where M = sup_val) you can use a bin sort,
which runs in time O(N+M):

for (i=0; i<N; ++i)
{
do
{
value = random_in_range(0, M-1);
} while(is_bit_set(value));

set_bit(value);
}
i=0;
for (j=0; j<M; ++j)
{
if (is_bit_set(j))
a[i++] = j;
}

But since M is much larger than N in your test, I doubt this would be
feasable.

-josh

[Keith Thompson]

Sam Dennis <sa*@malfunction.screaming.net> writes:

James Kanze wrote:

I think that most good C programmers are already writing a C++ subset.

So, for example, most good C programmers cast the return value of malloc
and friends, do they?

Good C programmers know enough not to care that their code won't compile
(or will function differently) when given to a C++ compiler.

[...]

With some rare exceptions. P.J. Plauger has stated here that he
actually has good reasons to write and distribute code that will
compiler either as C or as C++.

For most of us, however, worrying about whether our C code will
compile as C++ is a waste of time.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Christian Bau]

In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.org> wrote:

Sam Dennis <sa*@malfunction.screaming.net> writes:

James Kanze wrote:

I think that most good C programmers are already writing a C++ subset.

So, for example, most good C programmers cast the return value of malloc
and friends, do they?

Good C programmers know enough not to care that their code won't compile
(or will function differently) when given to a C++ compiler.

[...]

With some rare exceptions. P.J. Plauger has stated here that he
actually has good reasons to write and distribute code that will
compiler either as C or as C++.

For most of us, however, worrying about whether our C code will
compile as C++ is a waste of time.

One situation where you really want to make sure that your C code is
valid C++ with identical semantics: If you decide to move development
from C to C++ (that is change your code base from C to C++ and then
continue developing in C++), then changing your C code to the common
subset of C and C++ is an obvious first step.

The other situation is that of a library developer who wants lets say
valid C code, C++ code and Java code with the same functionality
(because customers demand all three versions). By using the common
subset of C and C++, he/she needs to write two different versions only
instead of three.

[James Kanze]

Sam Dennis <sa*@malfunction.screaming.net> writes:

|> James Kanze wrote:
|> > I think that most good C programmers are already writing a C++
|> > subset.

|> So, for example, most good C programmers cast the return value of
|> malloc and friends, do they?

Good point. There are probably a few other exceptions as well.

|> Good C programmers know enough not to care that their code won't
|> compile (or will function differently) when given to a C++ compiler.

I didn't say the contrary. On the other hand, the code written by good
C programmers will port quickly and easily to C++. It won't resemble
what is commonly called "idiomatic C++", but it will be correct,
compilable C++. The differences in semantics are minimal, and for the
most part, the features of C90 not available in C++ (like implicite
declaration of functions) are not considered good C either.

|> It is also possible to write C programs that function identically if
|> taken as other languages that are much more distantly related to C
|> than C++, but no-one is suggesting that writing for, say, FORTRAN
|> compatibility (this one may not be possible, but that's not the
|> point) is a good practice.

I'm not suggesting that targetting compatibility is good practice. I'm
saying that if you follow good C coding practices, you won't be far from
what is already legal C++.

--
James Kanze
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France [phone]

[James Kanze]

Keith Thompson <ks***@mib.org> writes:

|> Sam Dennis <sa*@malfunction.screaming.net> writes:
|> > James Kanze wrote:
|> > > I think that most good C programmers are already writing a C++
|> > > subset.

|> > So, for example, most good C programmers cast the return value of
|> > malloc and friends, do they?
|> > Good C programmers know enough not to care that their code won't
|> > compile (or will function differently) when given to a C++
|> > compiler.

|> [...]

|> With some rare exceptions. P.J. Plauger has stated here that he
|> actually has good reasons to write and distribute code that will
|> compiler either as C or as C++.

|> For most of us, however, worrying about whether our C code will
|> compile as C++ is a waste of time.

The one exception might be header files and interfaces -- it is actually
fairly frequent to use the same header file for C and C++.

--
James Kanze
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France [phone]

[unknown]

E. Robert Tisdale wrote:

- snip -

I use Mozilla to read news.
I can kill threads
but I don't know how to kill individual subscribers.

Get your self a good riflefile.

[Grumble]

E. Robert Tisdale wrote:

I use Mozilla to read news.
I can kill threads
but I don't know how to kill individual subscribers.
Can you tell me how to do this with Mozilla?
How would I killfile "Default User" for example?
Or do I need to get a different newsreader?
What newsreader are you using?
And what did you do to killfile "RoSsIaCrIiLoIA"?

Tools - Message Filters

Sender contains "Default User"

Action = Mark read or Delete or ...

[Dan Pop]

In <40**************@jpl.nasa.gov> "E. Robert Tisdale" <E.**************@jpl.nasa.gov> writes:

I use Mozilla to read news.
I can kill threads
You can do more than that.
but I don't know how to kill individual subscribers.
Can you tell me how to do this with Mozilla?

When setting the filter, click on "Subject" and a new menu will open.
Select "Sender" instead of "Subject".

Yeah, it could be more intuitive...

I use a text-based newsreader that doesn't attempt to be anything else but
a newsreader and that does an excellent job of that.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Michael Wojcik]

In article <ch*********************************@slb-newsm1.svr.pol.co.uk>, Christian Bau <ch***********@cbau.freeserve.co.uk> writes:

One situation where you really want to make sure that your C code is
valid C++ with identical semantics: If you decide to move development
from C to C++ (that is change your code base from C to C++ and then
continue developing in C++), then changing your C code to the common
subset of C and C++ is an obvious first step.

I'm not sure I agree. If I were changing the language a project was
written in, I think that ought to include proper redesign. There
might well be significant reuse of the old C code in the new C++
implementation, but simply rewriting the code in the "common subset"
and recompiling strikes me as a very bad idea indeed.

I don't believe good C code is generally good C++ code. When
switching from one to the other, a rewrite is in order. (Yes, it
would be quicker to simply force the C into some shape that the C++
compiler would accept. That's the sort of reasoning which has
produced the current miserable state of most software.)

--
Michael Wojcik mi************@microfocus.com

Pocket #9: A complete "artificial glen" with rocks, and artificial moon,
and forester's station. Excellent for achieving the effect of the
sublime without going out-of-doors. -- Joe Green

[Dan Pop]

In <pa****************************@sig.now> August Derleth <se*@sig.now> writes:

On Fri, 21 May 2004 17:58:42 +0000, Mark A. Odell wrote:

Okay, maybe 14 years of C programming experience vs. zero for C++ is the
real reason but I still think it's weird.

I think most C programmers can pick up a C++ subset fairly easily, if they
have a good book.

Yup: the subset shared by the two languages ;-)

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Dan Pop]

In <sl****************@ID-227112.user.uni-berlin.de> Sam Dennis <sa*@malfunction.screaming.net> writes:

James Kanze wrote:

I think that most good C programmers are already writing a C++ subset.

So, for example, most good C programmers cast the return value of malloc
and friends, do they?

Let's put back the text you've abusively removed from James' post, in
order to make your cheap shot:

The actual incompatibilities in the common subset are fairly minor,
and most of C90 is in the common subset.

Did he or did he not *explicitly* aknowledge the existence of
incompatibilities? Or do you consider the void pointer issue involved in
your example as a *major* incompatibility?

To amend the original statement: most good C programmers are already
capable of writing in a C++ subset. The good question is whether such
code counts as *good* C++ code?...

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Mabden]

"Dan Pop" <Da*****@cern.ch> wrote in message
news:c8**********@sunnews.cern.ch...

In <40**************@jpl.nasa.gov> "E. Robert Tisdale" <E.**************@jpl.nasa.gov> writes:

I use Mozilla to read news.
I can kill threads

You can do more than that.

but I don't know how to kill individual subscribers.

Ooooh! Ooooh! Pick me! Pick me!

--
Mabden

[RoSsIaCrIiLoIA]

On Sat, 22 May 2004 18:52:08 GMT, josh
<sm*************************@yahoo.com.NOSPAM> wrote:

RoSsIaCrIiLoIA wrote:

On Fri, 21 May 2004 20:05:20 GMT, josh wrote:

>It should be possible to get a sorted array of random distinct integers
>in time O(N),

How?

lower_bound = minimum;
upper_bound = maximum - number_of_slots;
for (index=0; index<number_of_slots; ++index)
{
a[index] = random_in_range(lower_bound, upper_bound);
lower_bound = a[index]+1;
++upper_bound;
}
I don't understand, but that seems to me like this

The requirement for a sorted array is that a[i] is greater than a[i-1]

[...]So a[0] must be chosen in [0, sup_val-N]

Next we choose a[1], which must be greater than a[0] and still leave
room for all the rest of the array. Since there are 1 fewer integers
above a[0] than above a[1], we can just bump the upper bound by 1.

So a[1] must be chosen in [a[0]+1, sup_val-N+1]

We then continue at each step by taking the previous value as a lower
bound and increasing the upper bound by 1:

a[2] must be in [a[1]+1, sup_val-N+2]
a[3] must be in [a[2]+1, sup_val-N+3]
a[4] must be in [a[3]+1, sup_val-N+4]
...
a[N-2] must be in [a[N-3]+1, sup_val-2]
a[N-1] must be in [a[N-2]+1, sup_val-1]
(and of course there is no a[N])

So in general, a[i] must be chosen in [a[i-1]+1, sup_val-N+i]:

a[o] = random_in_range(0, sup_val-N);
for (i=1; i<N; ++i)
a[i] = random_in_range(a[i-1]+1, sup_val-N+i);

and the code above should do exactly the same thing. [...] Mine can
generate all of them, although I suspect the probability distribution
may be different.

thank you
but seems to me there are odd results e.g.
if rand_array is like you suggest =>

inserisci il massimo[0 finisce]> 888888888
inserisci il numero di elementi> 20
312557105 548251158 760618515 876091816 886173925 888503572 888804673
888826177
888871515 888882642 888884513 888885725 888887085 888888029 888888553
888888700
888888768 888888843 888888873 888888877
inserisci il massimo[0 finisce]> 0

rand_array1 seems 'ok'
inserisci il massimo[0 finisce]> 99
inserisci il numero di elementi> 98
0 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 5
6 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 84 85 86 87 88 89 90 91 92 93 94 95 96 97
inserisci il massimo[0 finisce]> 300
inserisci il numero di elementi> 50
4 5 6 11 17 24 25 29 44 47 58 60 63 70 82 85 94 98 99 103 108 120 127
130 132 1
43 150 151 165 166 167 176 191 192 195 201 210 214 216 230 233 245 246
248 263 2
64 272 274 275 277
inserisci il massimo[0 finisce]> 300
inserisci il numero di elementi> 50
1 4 8 10 22 25 31 40 47 49 52 53 54 67 77 86 87 92 105 113 114 119
128 133 136
142 146 147 163 166 173 184 191 197 203 207 215 218 223 232 234 241
242 254 256
263 269 274 280 281
inserisci il massimo[0 finisce]> 8888888
inserisci il numero di elementi> 10
539728 635645 1238316 1973567 2832166 2844598 4184902 5806132 6061761
7364582
inserisci il massimo[0 finisce]> 0

/* C++ and C but you use a C++ compiler and try ... */
#include <iostream.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
#define U unsigned
#define F for
#define W while
#define R return
#define os cout <<
#define is cin >>

int
BogusRandArray( U* a, U size, U max_val)
{static int i = 1;
unsigned j, t, m1;
double m, u;
/*---------------------*/
if( a==0 || size<2 || max_val<=size )
return 0;
if(i)
{i = 0; srand(time(0));}

m = (double) UINT_MAX/(size+1); m1 = m;
a[0] = (U) _lrand() % m1;
for( j = 1; j<size; ++j)
a[j] = a[j - 1] + 1 + (U) _lrand() % m1;
if(a[size - 1] > max_val)
{
m = (double) max_val/ size; m1 = m;
u = (double)(size - 1) * m + (double)((U) _lrand() % m1);
/* os "u==" << u << "(size)*m=" << (size)*m; */
u = ( (double) a[size - 1] / u );
for( j = 0, t = 0; j<size; ++j)
{
a[j] = (double) a[j] / u;
if(a[j] <= t && j!=0)
++a[j];
t = a[j];
}
}
return 1;
}

U rand_array( U* a, U size, U sup_val )
{static int i = 1;
unsigned j, k, h;
/*---------------------*/
if( a==0 || size<2 || sup_val<=size )
return 0;
if(i)
{i = 0; srand(time(0));}

h = sup_val - size;
a[0] = (U) _lrand() % h;

for( j = 1; j<size; ++j)
a[j] = a[j-1] + 1 + (U) _lrand() % (h - a[j-1]-1 + j);
R 1;
}
U intervallo(U a, U b)
{R a + (U) _lrand() % (b-a);}

U rand_array1( U* a, U size, U sup_val )
{static int i = 1;
unsigned j, k, h;
/*---------------------*/
if( a==0 || size<2 || sup_val<=size )
return 0;
if(i)
{i = 0; srand(time(0));}

k = sup_val / size;
a[0] = (k<=1 ? 0 : (U) _lrand() % k);

for( j = 1; j<size; ++j)
a[j] =
(a[j-1]+1 >= (h=j*k)
? a[j-1] + 1
: intervallo( a[j-1] + 1, h)
);
R 1;
}

/* it is a c++ main */
int main(void)
{U a[100] = {0}, i, j=1, k, z;
/*--------------------------------*/
W(j!=0)
{
os "inserisci il massimo[0 finisce]> "; is j;
if(j==0) break;
os "inserisci il numero di elementi> "; is k;
if(k>100) {os "Troppi elementi\n";continue;}
z = rand_array1( a, k, j);
if(z)
{
F( i = 0; i<k; ++i)
os " " << a[i];
os "\n";
}
else os "Errore\n";
}
R 0;
}

[Michael Wojcik]

In article <96************************@posting.google.com>, re********@yahoo.com (red floyd) writes:

"Allan Bruce" <al*****@TAKEAWAYf2s.com> wrote in message news:<c8**********@news.freedom2surf.net>...

[snip]

value = (unsigned)rand()/(RAND_MAX/NUM_ELEMENTS);

for (loop=1; loop<NUM_ELEMENTS; loop++)
{
array[loop] = value;
value += (unsigned)rand()/(RAND_MAX/NUM_ELEMENTS);
}

Unsorted and you don't fill array[0].

array[0] is not set, true; but barring overflow that looks sorted to
me. value increases (or remains the same) on each loop iteration.

--
Michael Wojcik mi************@microfocus.com

Recently, they appeared at the reopening of the Brookdale Library,
luring passersby with the opportunity to be anonymously silly.

[Keith Thompson]

RoSsIaCrIiLoIA <[e-mail]> writes:
[...]

#define U unsigned
#define F for
#define W while
#define R return
#define os cout <<
#define is cin >> [...] /* it is a c++ main */

[...]

Please stop wasting our time.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[CBFalconer]

RoSsIaCrIiLoIA wrote:

.... snip ...
/* C++ and C but you use a C++ compiler and try ... */
#include <iostream.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
#define U unsigned
#define F for
#define W while
#define R return
#define os cout <<
#define is cin >>

You have been told many times not to do this here. rePLONK.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[RoSsIaCrIiLoIA]

On Tue, 25 May 2004 16:53:50 GMT, RoSsIaCrIiLoIA <[e-mail]> wrote:

Do has this soulution as result a 'random' array

#define U unsigned
#define F for
#define W while
#define R return

U rand_array2( U* a, U size, U sup_val )
{static int i = 1;
unsigned j, h;
double d, v;
/*---------------------*/
if( a==0||size==0||sup_val<=size )
R 0;
if(i)
{i = 0; srand( (U) time(0) );}

label:
F( j=0, a[0]=UINT_MAX; j<size; ++j)
{
h = _lrand() % sup_val;
if(a[0]>h) a[0] = h;
}
if(a[0] > sup_val - size)
goto label;

d = ( (double)sup_val - a[0] ) / (size - 1);
if( (unsigned) d <= 1u )
a[0] = 0;
for( j = 1; j<size; ++j)
a[j] =
(a[j-1]+1 >= (h=(double) a[0] + d*j)
? a[j-1] + 1
: intervallo( a[j-1] + 1, h)
);
R 1;
}

like this

void
ArrRand(unsigned* a, unsiged size, unsigned superiore)
{static int m = 1;
unsigned i, j, h, temp;

if(a==0 || size<2 || superiore==0)
return;
if(m)
{ m = 0; srand(time(0));}
for( i = 0; i < size; ++i)
{label:
a[i] = _lrand() % superiore; /*_lrand is for Borland */
for( j = 0; j < i; ++j) /* if not, use your_lrand() */
{if(a[i] == a[j]) goto label;
else if(a[i] < a[j]) /* that fill an unsigned */
{temp = a[i];
for( h = i; h > j; --h)
a[h] = a[h - 1];
a[j] = temp;
break;
}
}
}
}

? Is it O(N)?
It is a silly function that find random number where to calculate in
a loop e.g.
array(a, 100,7000000);
cont=0; j=0;
while(++cont<7000000 && j<100)
{
if(cont==a[j]){++j; calaculate..}
....
}

[Nick Keighley]

RoSsIaCrIiLoIA <[e-mail]> wrote in message news:<1v********************************@4ax.com>. ..

<snip>

int main(void)
{unsigned a[100] = {0}, i;

ArrRand( a, (sizeof a)/(sizeof *a), 80000000);
for( i = 0; i < 99; ++i)

this only prints 99 items

cout << " " << a[i];
cout << "\n";
return 0;
}

--
Nick Keighley

[E. Robert Tisdale]

Grumble wrote:

E. Robert Tisdale wrote:

I use Mozilla to read news.
I can kill threads
but I don't know how to kill individual subscribers.
Can you tell me how to do this with Mozilla?
How would I killfile "Default User" for example?
Or do I need to get a different newsreader?
What newsreader are you using?
And what did you do to killfile "RoSsIaCrIiLoIA"?

Tools - Message Filters

Sender contains "Default User"

Action = Mark read or Delete or ...

Thanks Grumble,

I just installed Mozilla 1.6 and this seemed to work.

[josh]

RoSsIaCrIiLoIA wrote:

On Sat, 22 May 2004 18:52:08 GMT, josh
<sm*************************@yahoo.com.NOSPAM> wrote:

Mine can
generate all of them, although I suspect the probability distribution
may be different.
thank you
but seems to me there are odd results e.g.
if rand_array is like you suggest =>

inserisci il massimo[0 finisce]> 888888888
inserisci il numero di elementi> 20
312557105 548251158 760618515 876091816 886173925 888503572 888804673
888826177
888871515 888882642 888884513 888885725 888887085 888888029 888888553
888888700
888888768 888888843 888888873 888888877
inserisci il massimo[0 finisce]> 0

This could come out of a "generate random and sort" algorithm, although
most likely with a lower probability than here. Your code below, if I
understand it correctly, cannot generate this sequence given that input.

It looks like it does create sequences with a different probability
distribution. That should be fixable by using something other than a
uniform random number generator, although exactly how non-uniform might
be difficult to figure out.

Another possibility might be to choose the middle element in the array
and then recursivly fill the top and bottom halves, using a similar
method for selecting the upper and lower bounds. Or this can probably
be done iteritavely, but it would take more thought. Either way it'd
still take O(N) time.
rand_array1 seems 'ok'
inserisci il massimo[0 finisce]> 99
inserisci il numero di elementi> 98
0 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 5
6 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 84 85 86 87 88 89 90 91 92 93 94 95 96 97
If I understand your code correctly, this is the only sequence that this
can generate for this input, despite there being ~99 different sequences
that fit the requirements. (eg, 1 2 3 ... 96 97 98)
U intervallo(U a, U b)
{R a + (U) _lrand() % (b-a);}

U rand_array1( U* a, U size, U sup_val )
{static int i = 1;
unsigned j, k, h;
/*---------------------*/
if( a==0 || size<2 || sup_val<=size )
return 0;
if(i)
{i = 0; srand(time(0));}

k = sup_val / size;
a[0] = (k<=1 ? 0 : (U) _lrand() % k);

for( j = 1; j<size; ++j)
a[j] =
(a[j-1]+1 >= (h=j*k)
? a[j-1] + 1
: intervallo( a[j-1] + 1, h)
);
R 1;
}

This code is hurting my brain. I assume it would be equivalent to this?

unsigned intervallo(unsigned low, unsigned high)
{
return low + (unsigned)_lrand() % (high-low);
}

unsigned rand_array1(unsigned *a, unsigned size, unsigned sup_val)
{
static int rand_seeded = 0;
unsigned i, window, limit;

if (a==0 || size<2 || sup_val<=size)
return 0;

if (!rand_seeded)
{
rand_seeded = 1;
srand(time(0));
}

window = sup_val / size;
if (window <= 1)
a[0] = 0;
else
a[0] = intervallo(0, window);

for (i=1; i<size; ++i)
{
limit = i*window;
if (a[i-1]+1 >= limit)
a[i] = a[i-1]+1;
else
a[i] = intervallo(a[i-1]+1, limit);
}
}

It is possible, though extremely unlikely, that a sorted random set of
10 integers in [0, 1000) comes out to:
990 991 992 993 994 995 996 997 998 999

With this code, that is completely impossible.

There's also some rounding issues, where you will never get 996 if you
use a range of [0, 997) for nearly any array size.

-josh

[josh]

josh wrote:

Another possibility might be to choose the middle element in the array
and then recursivly fill the top and bottom halves, using a similar
method for selecting the upper and lower bounds. Or this can probably
be done iteritavely, but it would take more thought. Either way it'd
still take O(N) time.

This still isn't quite right.

It occurs to me that the center value, which would be the median of the
set, should be close to the average of the set and thus approximately
normal with certain properties. So you need random numbers with a
normal distribution rather than uniform. I'm using code from "The
Ziggurat Method for Generating Random Variables" by George Marsaglia and
Wai Wan Tsang, which should be available online somewhere. (The
included code isn't terribly nice, but the algorithm is.)

From the central limit theorem:
- the sample mean will be the mean of the population
mean = (range_low + range_high)/2;
- the standard deviation of the sample mean will be the standard
deviation of the population / sqrt( sample size )
stddev = pop_stddev / sqrt(size);

from http://mathworld.wolfram.com/UniformDistribution.html
the population variance is (b-a)^2/12, so the population standard
deviation should be (b-a)/sqrt(12) and
stddev = (range_high - range_low) / sqrt(12*size);

so:

#include <math.h> /* for sqrt */

unsigned normal_in_range(unsigned low, unsigned high, double stddev)
{
/* RNOR from the paper mentioned above */
unsigned r = (unsigned)(RNOR * stddev) + (high+low)/2;
if (r >= high) r = high-1;
if (r < low) r = low;
if (r >= high) r = low; /* in case high==0 */
return r;
}

unsigned sorted_random_array_r(
unsigned *base, unsigned index_low, unsigned index_high,
unsigned range_low, unsigned range_high)
{
const unsigned index_mid = (index_low + index_high)/2;
const unsigned count_below = index_mid-index_low;
const unsigned count_above = index_high-index_mid;
double stddev;

if (index_low >= index_high)
return 0;

stddev = (range_high-range_low)/sqrt(12*(index_high-index_low));

base[index_mid] = normal_in_range(range_low+count_below,
range_high-count_above, stddev);

return 1
+ sorted_random_array_r(base, index_low, index_mid,
range_low, base[index_mid])
+ sorted_random_array_r(base, index_mid+1, index_high,
base[index_mid]+1, range_high);
}

/* returns size on success, 0 if inputs are invalid */
unsigned sorted_random_array(unsigned *base,
unsigned size, unsigned range)
{
if (range < size)
return 0;

return sorted_random_array_r(base, 0, size, 0, range);
}

That gives numbers that look very much like a sorted uniformly random
set in (I hope) O(N) time. That is, not only can it generate the same
sequences as a naive "fill and sort" algorithm, it seems to generate
them with the same probability. (as it theoretically should)

One call to sorted_random_array(, 20, 888888888) gives:
41889677, 53715473, 131865038, 207767453, 234227055, 262409187,
277295135, 333417643, 364713486, 414888301, 472025225, 482934207,
490867513, 539655409, 716275231, 755247825, 776187269, 783141470,
814645472, 871172337

A similar call to a naive "fill and sort" algorithm gives:
11622284, 28435660, 103962880, 110241564, 115014999, 211959552,
279580988, 339350979, 480464091, 503398153, 519736592, 521628837,
553710371, 624480689, 629627559, 676032821, 711727532, 809860628,
809976730, 847242980

Looks pretty good to me.

-josh