Printable View
Hi,
I have a problem that I'm really stumped on. The problem is this:
Suppose that a[] is an array of integers of size 100, and that for each i
a. the element a[i] has value i
b. the element a[i] has value 99-i
If quicksort(a, a + 99) is invoked, how many function calls to quicksort() are made? Write your program which will test quicksort(), and compute and print the number of recursive calls to quicksort() for a. and b.
Can anyone help me figure this out/explain it to me?
Start by incrementing a counter inside quicksort every time it's called:
Code:#include <stdio.h>
static int number_of_calls;
void f()
{
static int i;
if (i++ == 10)
return;
number_of_calls++;
f();
}
int main(void)
{
f();
printf("%d calls to f()\n", number_of_calls);
return 0;
}
Ok, thanks. That helped a bit but I'm still a little confused. I still need to write quicksort(a, a + 99). Do I just declare an array of size 100 in the number_of_calls function or should I create a new file altogether? Please bare with me, I'm still new to C. Thanks! :)
It appears as if you want an array of size 100.
*bangs head on desk*
I must be stupid or something, lol!
I tried a few things (what is commented out):
#include <stdio.h>
//#define N 100
//int A[] = {100};
//quicksort(list, 0, 99);
//void quicksort (int *, int, int);
static int number_of_calls;
void f()
{
static int i;
if (i++ == 10)
return;
number_of_calls++;
f();
}
int main(void)
{
f();
printf("%d calls to f()\n", number_of_calls);
return 0;
}
Unfortunately the book I have doesn't really help me much. What am I doing wrong?
What is the size of the array? are there supposed to be 100 elements, or does every element have to be set to 100? - edit - if every element has to be 100, how many elements are there supposed to be?
It sounds similar to this.
If you want help doing this to your quicksort code, post the code that you have.Code:#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int compares = 0;
int mycmp(const void *a, const void *b)
{
const int *x = a;
const int *y = b;
++compares;
if ( *x < *y )
{
return -1;
}
if ( *x > *y )
{
return 1;
}
return 0;
}
void fill(int *array, int size)
{
int i;
for ( i = 0; i < size; ++i )
{
*array++ = rand() % size;
}
}
void show(const int *array, int size)
{
int i;
for ( i = 0; i < size; ++i )
{
printf(" %2d%c", *array++, i % 16 == 15 ? '\n' : ',');
}
puts("\n");
}
int main(void)
{
int a[100];
srand(time(NULL));
fill(a, sizeof(a)/sizeof(*a));
show(a, sizeof(a)/sizeof(*a));
qsort(a, sizeof(a)/sizeof(*a), sizeof(*a), mycmp);
show(a, sizeof(a)/sizeof(*a));
printf("compares = %d\n", compares);
return 0;
}
/* my output
33, 82, 91, 36, 24, 22, 54, 81, 44, 24, 33, 28, 71, 69, 57, 90
99, 9, 14, 56, 8, 72, 63, 13, 37, 48, 8, 8, 60, 41, 91, 64
12, 46, 23, 14, 58, 89, 70, 63, 27, 74, 46, 3, 24, 76, 2, 28
63, 28, 65, 78, 45, 78, 71, 31, 4, 9, 7, 38, 47, 98, 88, 17
91, 23, 19, 11, 60, 85, 93, 47, 36, 28, 29, 58, 87, 74, 24, 14
35, 98, 20, 12, 62, 65, 78, 75, 46, 46, 48, 94, 72, 18, 78, 59
87, 59, 8, 16,
2, 3, 4, 7, 8, 8, 8, 8, 9, 9, 11, 12, 12, 13, 14, 14
14, 16, 17, 18, 19, 20, 22, 23, 23, 24, 24, 24, 24, 27, 28, 28
28, 28, 29, 31, 33, 33, 35, 36, 36, 37, 38, 41, 44, 45, 46, 46
46, 46, 47, 47, 48, 48, 54, 56, 57, 58, 58, 59, 59, 60, 60, 62
63, 63, 63, 64, 65, 65, 69, 70, 71, 71, 72, 72, 74, 74, 75, 76
78, 78, 78, 78, 81, 82, 85, 87, 87, 88, 89, 90, 91, 91, 91, 93
94, 98, 98, 99,
compares = 594
*/
Well I have this code but I don't think it's correct:
#define N 100 /* size of array, and four macros below */
#define swap(x, y) { int t; t = x; x = y; y = t;}
#define order(x, y) if (x > y) swap(x, y)
#define o2(x, y) order(x, y)
#define o3(x, y, z) o2(x, y); o2(x, z); o2(y, z)
typedef enum {yes, no} yes_no; /*enumeration type yes_no */
static yes_no find_pivot(int *left, int *right,
int *pivot_ptr);
static int *partition(int * left, int *right, int pivot);
/* static functions - known only in this file */
int i;
int main(void)
{
double a[N];
for(i = 0; i < N; i++);
scanf("%f", &a[i]);
quicksort(a, a + N -1);
for (i = 0; i < N, i++) printf("%f", a[i]);
putchar('\n');
return 0;
}
void quicksort(int *left, int *right) /* recursive algorithm */
{
int *p, pivot;
if (find_pivot(left, right, &pivot) == yes) {
p = partition(left, right, pivot);
/* moving all elements < pivot to left partition, */
/* and >= 0 to right partition */
quicksort(left, p - 1);
quicksort(p, right);
}
}
static yes_no find_pivot(int *left, int *right,
int *pivot_ptr)
/* pivot is attempted to be different than the smallest value of 3 args */
{
int a, b, c, *p;
a = *left; /* left value */
b = *(left + (right - left) / 2); /* middle value */
c = *right; /* right value */
o3(a, b, c); /* order a, b, c */
if (a < b) { /* pivot will be b */
*pivot_ptr = b;
return yes;
}
if (b < c) { /* a == b, pivot will be c */
*pivot_ptr = c;
return yes;
}
for (p = left +1; p <= right; ++p)
/* trying to find another pivot != left */
if (*p != * left) {
*pivot_ptr = (*p < *left) ? *left : *p;
return yes;
}
return no; /* all elements of an array have the same value */
}
static int *partition(int *left, int *right, int pivot)
{
while (left <= right) {
while (*left < pivot)
++left; /* no action */
while (*right >= pivot)
--right;
if (left < right) { /* exchanging value to keep < ordering */
swap(*left, *right);
++left;
--right;
}
}
return left;
}
I just took a quick pass through this.
[edit]Code:#include<stdio.h>
#define N 100 /* size of array, and four macros below */
#define swap(x, y) { int t; t = x; x = y; y = t;}
#define order(x, y) if (x > y) swap(x, y)
#define o2(x, y) order(x, y)
#define o3(x, y, z) o2(x, y); o2(x, z); o2(y, z)
typedef enum
{
yes, no
} yes_no; /*enumeration type yes_no */
/* pivot is attempted to be different than the smallest value of 3 args */
static yes_no find_pivot(int *left, int *right, int *pivot_ptr)
{
int a, b, c, *p;
a = *left; /* left value */
b = *(left + (right - left) / 2); /* middle value */
c = *right; /* right value */
o3(a, b, c); /* order a, b, c */
if ( a < b )
{ /* pivot will be b */
*pivot_ptr = b;
return yes;
}
if ( b < c )
{ /* a == b, pivot will be c */
*pivot_ptr = c;
return yes;
}
for ( p = left +1; p <= right; ++p )
{ /* trying to find another pivot != left */
if ( *p != * left )
{
*pivot_ptr = (*p < *left) ? *left : *p;
return yes;
}
}
return no; /* all elements of an array have the same value */
}
static int *partition(int *left, int *right, int pivot)
{
while ( left <= right )
{
while ( *left < pivot )
{
++left; /* no action */
}
while ( *right >= pivot )
{
--right;
}
if ( left < right )
{ /* exchanging value to keep < ordering */
swap(*left, *right);
++left;
--right;
}
}
return left;
}
int count = 0;
void quicksort(int *left, int *right) /* recursive algorithm */
{
int *p, pivot;
++count;
if ( find_pivot(left, right, &pivot) == yes )
{
p = partition(left, right, pivot);
/* moving all elements < pivot to left partition, */
/* and >= 0 to right partition */
quicksort(left, p - 1);
quicksort(p, right);
}
}
int main(void)
{
int i;
int a[N] =
{
33, 82, 91, 36, 24, 22, 54, 81, 44, 24, 33, 28, 71, 69, 57, 90,
99, 9, 14, 56, 8, 72, 63, 13, 37, 48, 8, 8, 60, 41, 91, 64,
12, 46, 23, 14, 58, 89, 70, 63, 27, 74, 46, 3, 24, 76, 2, 28,
63, 28, 65, 78, 45, 78, 71, 31, 4, 9, 7, 38, 47, 98, 88, 17,
91, 23, 19, 11, 60, 85, 93, 47, 36, 28, 29, 58, 87, 74, 24, 14,
35, 98, 20, 12, 62, 65, 78, 75, 46, 46, 48, 94, 72, 18, 78, 59,
87, 59, 8, 16,
};
quicksort(a, a + N -1);
for ( i = 0; i < N; i++ )
{
printf("%2d,%c", a[i], i % 16 == 15 ? '\n' : ' ');
}
putchar('\n');
printf("count = %d\n", count);
return 0;
}
/* my output
2, 3, 4, 7, 8, 8, 8, 8, 9, 9, 11, 12, 12, 13, 14, 14,
14, 16, 17, 18, 19, 20, 22, 23, 23, 24, 24, 24, 24, 27, 28, 28,
28, 28, 29, 31, 33, 33, 35, 36, 36, 37, 38, 41, 44, 45, 46, 46,
46, 46, 47, 47, 48, 48, 54, 56, 57, 58, 58, 59, 59, 60, 60, 62,
63, 63, 63, 64, 65, 65, 69, 70, 71, 71, 72, 72, 74, 74, 75, 76,
78, 78, 78, 78, 81, 82, 85, 87, 87, 88, 89, 90, 91, 91, 91, 93,
94, 98, 98, 99,
count = 125
*/
I had made a number of changes from int to double (since your array was doubles, but the code appeared to be sorting ints). And then I decided to just sort ints instead.
[/edit]
I didn't feel like manually entering in 100 values. And [code] [/code] tags make things look nice.
Ok, thanks for that, it's helped me out alot! :)