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 = _lrand() % superiore; /*_lrand is for Borland */
for( j = 0; j < i; ++j) /* if not, use your_lrand() */
{if(a == a[j]) goto label;
else if(a < a[j]) /* that fill an unsigned */
{temp = a;
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;
cout << "\n";
return 0;
}

 

[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 = _lrand() % superiore; /*_lrand is for Borland */

a = (unsigned) _lrand() % superiore;

 

[josh]

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 = _lrand() % superiore; /*_lrand is for Borland */
for( j = 0; j < i; ++j) /* if not, use your_lrand() */
{if(a == 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 < a[j]) /* that fill an unsigned */

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

{temp = a;
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;
cout << "\n";

What about poor neglected a[99]?

return 0;
}

-josh

 

[Allan Bruce]

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]

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 <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 = _lrand() % superiore; /*_lrand is for Borland */
for( j = 0; j < i; ++j) /* if not, use your_lrand() */
{if(a == 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 < a[j]) /* that fill an unsigned */

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

{temp = a;
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;
cout << "\n";

What about poor neglected a[99]?

I forgot it

 

[Mark A. Odell]

#include <iostream.h>

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

 

[Martin Ambuhl]

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]

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.

 

[red floyd]

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]

I thought it was a C++ header file.

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

 

[Mark A. Odell]

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

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

 

[Alex Monjushko]

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

 

[Mark A. Odell]

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.

 

[Keith Thompson]

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.

 

[Default User]

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

 

[Default User]

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

 

[josh]

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).

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)

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;
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

 

[E. Robert Tisdale]

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]

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