MIME-Version: 1.0
Server: CERN/3.0
Date: Sunday, 24-Nov-96 22:46:43 GMT
Content-Type: text/html
Content-Length: 2963
Last-Modified: Friday, 15-Nov-96 18:02:45 GMT
CS100B Program 5 Clarifications
CS100B Program 5 Clarifications
14 November 1996
Added: 13 November 1996
Part 4
Part 4 asks you to compare the running time of Parts 2 and 3. Unfortunately,
since we're sorting only 256 elements, both parts execute in less than a
second. So, for Part 4, answer this question: Which part (2 or 3) should
execute faster? Why?
Added: 13 November 1996
make_array_3
In make_array_3, I say that it has one argument,
array. Then, in the function, it refers to a.
These should be the same. So, the function should be:
void make_array(elemptr a[256])
{
int i;
for (i = 0; i < 256; i++)
{
a[i] = (elemptr)malloc(sizeof(elem));
if (a[i] == NULL)
{
printf("Error: out of memory at %d\n", i);
exit(1);
}
a[i]->x = rand() % 99 + 1;
}
}
Added: 8 November 1996
Mac Memory Limits
Macs have a memory limit that you can statically declare only 32k bytes of
data. As a result, we have to change the number of things that you have to
sort.
Part 1
Each int is 4 bytes, so 32k should be able to fit 8k ints. However, we need
a little room for additional stuff (like function calls, which take up
memory), so we'll only sort 4096 integers. For the output, print every 64th
integer, 8 per line.
Only the size of the array in make_array_1 changes.
Part 2
Each elem is 1k bytes, so we could only fit 32. As a result, we'll
dynamically allocate the array. You don't know how to do this, so I'll
give you the code. We will sort an array of 256 elems, printing every 4th
for output. Change make_array_2 to:
void make_array_2(elem **a)
{
int i;
*a = (elem *)malloc(256 * sizeof(elem));
if (*a == NULL)
{
printf("Error: out of memory!\n");
exit(1);
}
for (i = 0; i < 256; i++)
(*a)[i].x = rand() % 99 + 1;
}
Also, your main should be:
void main(void)
{
elem *a;
make_array_2(&a);
/* you add the rest of the code */
}
Recall the array/pointer duality presented in class. "a" is a pointer to an
elem. However, we dynamically allocated an array for "a" to point to. As a
result, "a[0]" is the first element of that array, and "a[255]" is the last
element. In your quicksort function, you can treat "a" as though it was an
array of elems.
Part 3
We will sort an array of 256 pointers to elems, printing every 4th
for output. Only the size of the array in make_array_3 changes.
Added: 7 November 1996
Partitioning Example
There is a very minor typo in the partitioning example. On page 3,
in the third line, it says "However, since l < r...". This should be "r < l".