C help OR pointers are a spawn of Satan

MasterDebater

Right, so I've got a project where I've got to take several data files, sort them using sorting algorithm of your choice, time how long it takes, etc etc. Simple stuff.

The problem is that we've got to make the datafiles ourselves. Since I'm using qsort in C, this means arrays. Got that code working, but when I try to pass the random array to the main function, gcc doesn't like something.

Snippets:
My random function

int* randomArray(int scale)
{
        int length = INT_MAX / scale;
        int arr[length];
        int index = 0;
        srand(clock());
        for(index = 0; index < length; index++)
        {
                arr[index] = rand();
        }
        return arr;
}

int main()
{
        time_t start, end;
        double sort1Time, sort2Time, sort3Time;
        int sort1[INT_MAX / 4], sort2[INT_MAX / 16], sort3[INT_MAX / 256];

        sort1 = randomArray(4);
        sort2 = randomArray(16);
        sort3 = randomArray(256);
.
.
.(operations on the arrays)

The problem occurs when I try to assign sort1, sort2, and sort3. It says the types do not match.

mspencer

One problem I see: in function randomArray, arr[] is only defined inside that function. When that function exits, the memory allocated to arr[] is available for other things to allocate. So your program is not safe if you do that. Better idea: create the array (buffer) in main() and pass a pointer inside the function. You don't have to return anything -- your function's result can be read from the buffer, as a side-effect.

Second, function randomArray() returns a pointer to an int, but you are assigning that value to an int. You need to tell the computer "the result of randomArray() is a memory address. Dereference that address and you'll find a value. Put that value in sort1."

Finally, speaking as a Computer Science grad student taking a type systems class: yes pointers are a spawn of Satan -- but get used to them because they aren't going away.

Edit: oops, ah I see, the result is a buffer full of ints. Consider either using memcpy, or redesigning your program so each buffer is created in main(), a pointer to that buffer is passed to your function, and the function returns void but changes that buffer.

Edit2: I just tried it. The compiler agrees with me about that first thing. It says "warning: function returns address of local variable."

I just rewrote your code my way, and I'm having moral issues with just posting it. When is your program due? I'd like to see you work things out on your own (with a few hints here and there) instead of just giving you the answer.

Edit3: also, does the assignment say you MUST run each procedure and compare wall-clock time before and after? If you're running this code on a unix machine, the 'time' shell command will print the amount of user and system time consumed by any program. If you can write nine separate programs and run them from the command line with 'time' I think that'd give you more accurate runtime information.

Smasher

Unless it's part of your assignment, you probably want to try sorting much smaller data sets. On 32 bit processors INT_MAX is 2147483647. Sort1 has INT_MAX/4 elements, which means it has 500 million integers in it. That should raise a red flag in your mind. Since integers are 4 bytes, sort1 takes up 2 gigabytes of memory, and sort2 another 1/2 gig.

mspencer

On my machine INT_MAX was undefined until I #define'd it. He would have to #include <limits.h> to get the 'official' version, so he's probably defining it himself and making it something smaller.

MasterDebater

Here's my new version, which has now gone from not compiling to getting segfaults. An upgrade, methinks

int main()
{
        time_t start, end;
        double sort1Time, sort2Time, sort3Time;
        int sort1[SORT1], sort2[SORT2], sort3[SORT3];
        int index = 0;

        randomArray(SORT1, sort1);  <--- segfaulting here
        randomArray(SORT2, sort2);
        randomArray(SORT3, sort3);

void randomArray(int numElements, int arr[])
{
        int length = numElements;
        int index = 0;
        time_t seed;
        seed = time(NULL);
        srand(seed);
        for(index = 0; index < length; index++)
        {
                arr[index] = rand();
        }
}

Am I on the right track, or just wanking?

BTW, the assignment's due 2PM tomorrow. It said that I had to time the sorting of different sizes of data files (it's an algorithms class, so we're showing running time and all that).

His Corkiness

I think this will do it:

int main()
{
        time_t start, end;
        double sort1Time, sort2Time, sort3Time;
        int sort1[SORT1], sort2[SORT2], sort3[SORT3];
        int index = 0;

        randomArray(SORT1, &sort1[0]);
        randomArray(SORT2, &sort2[0]);
        randomArray(SORT3, &sort3[0]);

void randomArray(int numElements, int *arr)
{
        int length = numElements;
        int index = 0;
        time_t seed;
        seed = time(NULL);
        srand(seed);
        for(index = 0; index < length; index++)
        {
                arr[index] = rand();
        }
}

Passing "&sort1[0]" gives the function a pointer to the first element of the array. Using arr[index] basically says "Here's a pointer to the start of the array (arr), now move 'index' worth of integers forward and give me the data that's there".

mspencer

MasterDebater wrote:

Here's my new version, which has now gone from not compiling to getting segfaults. An upgrade, methinks

int main()
{
        time_t start, end;
        double sort1Time, sort2Time, sort3Time;
        int sort1[SORT1], sort2[SORT2], sort3[SORT3];
        int index = 0;

        randomArray(SORT1, sort1);  <--- segfaulting here
        randomArray(SORT2, sort2);
        randomArray(SORT3, sort3);

void randomArray(int numElements, int arr[])
{
        int length = numElements;
        int index = 0;
        time_t seed;
        seed = time(NULL);
        srand(seed);
        for(index = 0; index < length; index++)
        {
                arr[index] = rand();
        }
}

Am I on the right track, or just wanking?

BTW, the assignment's due 2PM tomorrow. It said that I had to time the sorting of different sizes of data files (it's an algorithms class, so we're showing running time and all that).

In randomArray() make the definition need int* arr instead of int arr[]. Otherwise you should be good to go.

His Corkiness

Doh, yeah, sort1 == &sort1[0]. Heh.

mspencer

His Corkiness wrote:

Doh, yeah, sort1 == &sort1[0]. Heh.

True. You can even approximate the behavior of &sort1[1] and &sort1[2], etc.

Semantically, (sort1+1) is equivalent to &sort1[1]. And (sort1+2) is equivalent to &sort1[2]. It looks like you're messing with fire, adding 1 or 2 bytes to the pointer address, but addition has a different meaning when one operand is a pointer to a datatype. When you use addition where one operand is a pointer and the other operand is an integer, the resulting address is offset by the integer multiplied by sizeof(DATATYPE).

Sevorak

Wait, this is exactly the assignment I had, also due at 2 today. Do you go to Cal Poly?