qsorting type int**

[beagle197]

Folks,

Attempting to q-sort an array of int pairs, e.g. {{0,1}, {0, 0}, ...}
allocated using malloc/calloc, but the arguments I'm passing to qsort
are producing the incorrect results (see listing 1). Works for auto
object duration (e.g. heap) as in listing 2. Any ideas?

Thanks,
BEA


/* listing 1 : using malloc/calloc */

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

int compare( const void *arg1, const void *arg2 ) {
printf("arg1 %d, %d\n", ((int *) arg1)[0], ((int *) arg1)[1]);
printf("arg2 %d, %d\n", ((int *) arg2)[0], ((int *) arg2)[1]);
fflush(stdout);

if (((int *) arg1)[0] > ((int *) arg2)[0]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
if (((int *) arg1)[1] > ((int *) arg2)[1]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
return 0;
} else if (((int *) arg1)[0] < ((int *) arg2)[0]) {
return 1;
}
} else
return 1;
}

int main(int argc, char *argv[]) {
int i;
int **x;

x = malloc(6 * sizeof(int *));

for (i = 0; i < 6; ++i) {
x = calloc(2, sizeof(int));
}

/* assignments */
x[0][0] = 1;
x[0][1] = 3;
x[1][0] = 0;
x[1][1] = 2;
x[2][0] = 2;
x[2][1] = 6;
x[3][0] = 0;
x[3][1] = 1;
x[4][0] = 1;
x[4][1] = 7;
x[5][0] = 2;
x[5][1] = 1;

for (i = 0; i < 6; ++i)
printf("%d, %d\n", x[0], x[1]);
printf("\n");
fflush(stdout);

/* Sort remaining args using Quicksort algorithm: */
qsort( (void *)x, 6, sizeof( x[0] ), compare );

printf("\n");
for (i = 0; i < 6; ++i)
printf("%d, %d\n", x[0], x[1]);

for (i = 0; i < 6; ++i) {
free(x);
}
free(x);
}




=====

/* listing 2: using heap store */

#include <stdlib.h>

int compare( const void *arg1, const void *arg2 ) {
printf("arg1 %d, %d\n", ((int *) arg1)[0], ((int *) arg1)[1]);
printf("arg2 %d, %d\n", ((int *) arg2)[0], ((int *) arg2)[1]);

if (((int *) arg1)[0] > ((int *) arg2)[0]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
if (((int *) arg1)[1] > ((int *) arg2)[1]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
return 0;
} else if (((int *) arg1)[0] < ((int *) arg2)[0]) {
return 1;
}
} else
return 1;
}

int main(int argc, char *argv[]) {
int i;
int x[6][2] = {
{1,3},
{0,2},
{2,6},
{0,1},
{1,7},
{2,1}};

for (i = 0; i < 6; ++i)
printf("%d, %d\n", x[0], x[1]);
printf("\n");

/* Sort remaining args using Quicksort algorithm: */
qsort( (void *)x, 6, sizeof( x[0] ), compare );

printf("\n");
for (i = 0; i < 6; ++i)
printf("%d, %d\n", x[0], x[1]);
}

 

[Ben Pfaff]

int compare( const void *arg1, const void *arg2 ) {
printf("arg1 %d, %d\n", ((int *) arg1)[0], ((int *) arg1)[1]);
printf("arg2 %d, %d\n", ((int *) arg2)[0], ((int *) arg2)[1]);
fflush(stdout);

if (((int *) arg1)[0] > ((int *) arg2)[0]) {

You're trying to treat these arguments as if they point to ints.
They don't. They point to int *s. Thus, you should be casting
them to int ** or, better yet, assigning them to a variable of
type "const int **".

return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
[...]

/* Sort remaining args using Quicksort algorithm: */
qsort( (void *)x, 6, sizeof( x[0] ), compare );

qsort isn't necessarily implemented as a quicksort.

The cast here should be unnecessary.

[...]

/* listing 2: using heap store */

I don't see any use of malloc in this version. Usually that's
what programmers mean when they say "heap".

 

[beagle197]

changing to (int **) from int * in listing 1 worked...
thanks

 

[Arthur J. O'Dwyer]

Attempting to q-sort an array of int pairs, e.g. {{0,1}, {0, 0}, ...}
allocated using malloc/calloc, but the arguments I'm passing to qsort
are producing the incorrect results (see listing 1). Works for auto
object duration (e.g. heap) as in listing 2. Any ideas?

First guess, without even looking at the code: You'll be trying to
treat int[2] as if it were int*, or vice versa. Let's see if I'm right...

/* listing 1 : using malloc/calloc */

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

int compare( const void *arg1, const void *arg2 ) {
printf("arg1 %d, %d\n", ((int *) arg1)[0], ((int *) arg1)[1]);
printf("arg2 %d, %d\n", ((int *) arg2)[0], ((int *) arg2)[1]);
fflush(stdout);

if (((int *) arg1)[0] > ((int *) arg2)[0]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
if (((int *) arg1)[1] > ((int *) arg2)[1]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
return 0;
} else if (((int *) arg1)[0] < ((int *) arg2)[0]) {
return 1;
}
} else
return 1;
}

Aaugh! Blecch! Ick! You shouldn't have any casts in your code, and
a straightforward comparison like this should be maybe five lines long,
at most. Here's something equivalent to what you wrote:

int compare( const void *va, const void *vb ) {
int *a = va;
int *b = vb;
printf("arg1 %d, %d\n", a[0], a[1]);
printf("arg2 %d, %d\n", b[0], b[1]);

if (a[0] > b[0]) {
return -1;
} else if (a[0] == b[0]) {
return (a[1] > b[1]) ? -1 : (a[0] < b[0]);
} else return 1;
}

Now, I notice two things: First, you have a couple of typos; you
write a[0] (or rather, ((int *)arg1)[0]) where you mean a[1] (or
rather, ((int *)arg1)[1]). So my code isn't really doing quite the
same thing as yours, because I'm not invoking undefined behavior
by falling off the end of the function without returning a value.

If you had compiled your code with warnings turned on ("gcc -W -Wall"),
you would have found this error at once.

The other thing I notice is that you're treating the input
arguments as if they were pointers to int, which is not the case ---
or if it is, then you're comparing different elements of the sorted
array, which isn't kosher at all. Let's see which is the case...

int main(int argc, char *argv[]) {
int i;
int **x;

x = malloc(6 * sizeof(int *));

x = malloc(6 * sizeof *x);

for (i = 0; i < 6; ++i) {
x = calloc(2, sizeof(int));

x = malloc(2 * sizeof *x);
'calloc' is only useful if you need the memory zeroed for some reason.
Since you immediately assign new values into it, you don't need it to
be zeroed.

/* assignments */ [snip]

for (i = 0; i < 6; ++i)
printf("%d, %d\n", x[0], x[1]);
printf("\n");
fflush(stdout);

You don't need to 'fflush' an output stream if you've just written a
newline to it; the newline flushes the stream by itself already.

/* Sort remaining args using Quicksort algorithm: */
qsort( (void *)x, 6, sizeof( x[0] ), compare );

qsort(x, 6, sizeof *x, compare);

....And here's the problem, exactly as I thought at first. You're trying
to qsort an array of 'int*', but your comparison function is written
(almost) as if you're trying to sort an array of 'int[2]'.

The comparison function for 'qsort' should be written this way, in
order to sort an array of T:

int compare(const void *va, const void *vb)
{
const T *a = va;
const T *b = vb;
return (*a < *b) ? -1 : (*a > *b);
}

Or if T is a small type, such as your int*:

int compare(const void *va, const void *vb)
{
T a = *(const T *)va;
T b = *(const T *)vb;
return (a < b) ? -1 : (a > b);
}

Therefore, what you wanted was:

int compare(const void *va, const void *vb)
{
int *a = *(int * const *)va;
int *b = *(int * const *)vb;
if (a[0] < b[0]) return -1;
if (a[0] > b[0]) return -1;
return (a[1] < b[1]) ? -1 : (a[1] > b[1]);
}

Five lines --- what'd I tell you?

HTH,
-Arthur

 

[beagle197]

Attempting to q-sort an array of int pairs, e.g. {{0,1}, {0, 0}, ...}
allocated using malloc/calloc, but the arguments I'm passing to qsort
are producing the incorrect results (see listing 1). Works for auto
object duration (e.g. heap) as in listing 2. Any ideas?

First guess, without even looking at the code: You'll be trying to
treat int[2] as if it were int*, or vice versa. Let's see if I'm right...

/* listing 1 : using malloc/calloc */

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

int compare( const void *arg1, const void *arg2 ) {
printf("arg1 %d, %d\n", ((int *) arg1)[0], ((int *) arg1)[1]);
printf("arg2 %d, %d\n", ((int *) arg2)[0], ((int *) arg2)[1]);
fflush(stdout);

if (((int *) arg1)[0] > ((int *) arg2)[0]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
if (((int *) arg1)[1] > ((int *) arg2)[1]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
return 0;
} else if (((int *) arg1)[0] < ((int *) arg2)[0]) {
return 1;
}
} else
return 1;
}

Aaugh! Blecch! Ick! You shouldn't have any casts in your code, and
a straightforward comparison like this should be maybe five lines long,
at most. Here's something equivalent to what you wrote:

int compare( const void *va, const void *vb ) {
int *a = va;
int *b = vb;
printf("arg1 %d, %d\n", a[0], a[1]);
printf("arg2 %d, %d\n", b[0], b[1]);

if (a[0] > b[0]) {
return -1;
} else if (a[0] == b[0]) {
return (a[1] > b[1]) ? -1 : (a[0] < b[0]);
} else return 1;
}

Now, I notice two things: First, you have a couple of typos; you
write a[0] (or rather, ((int *)arg1)[0]) where you mean a[1] (or
rather, ((int *)arg1)[1]). So my code isn't really doing quite the
same thing as yours, because I'm not invoking undefined behavior
by falling off the end of the function without returning a value.

If you had compiled your code with warnings turned on ("gcc -W -Wall"),
you would have found this error at once.

The other thing I notice is that you're treating the input
arguments as if they were pointers to int, which is not the case ---
or if it is, then you're comparing different elements of the sorted
array, which isn't kosher at all. Let's see which is the case...

int main(int argc, char *argv[]) {
int i;
int **x;

x = malloc(6 * sizeof(int *));

x = malloc(6 * sizeof *x);

for (i = 0; i < 6; ++i) {
x = calloc(2, sizeof(int));

x = malloc(2 * sizeof *x);
'calloc' is only useful if you need the memory zeroed for some reason.
Since you immediately assign new values into it, you don't need it to
be zeroed.

/* assignments */
[snip]

for (i = 0; i < 6; ++i)
printf("%d, %d\n", x[0], x[1]);
printf("\n");
fflush(stdout);

You don't need to 'fflush' an output stream if you've just written a
newline to it; the newline flushes the stream by itself already.

/* Sort remaining args using Quicksort algorithm: */
qsort( (void *)x, 6, sizeof( x[0] ), compare );

qsort(x, 6, sizeof *x, compare);

...And here's the problem, exactly as I thought at first. You're trying
to qsort an array of 'int*', but your comparison function is written
(almost) as if you're trying to sort an array of 'int[2]'.

The comparison function for 'qsort' should be written this way, in
order to sort an array of T:

int compare(const void *va, const void *vb)
{
const T *a = va;
const T *b = vb;
return (*a < *b) ? -1 : (*a > *b);

}

Or if T is a small type, such as your int*:

int compare(const void *va, const void *vb)
{
T a = *(const T *)va;
T b = *(const T *)vb;
return (a < b) ? -1 : (a > b);

}

Therefore, what you wanted was:

int compare(const void *va, const void *vb)
{
int *a = *(int * const *)va;
int *b = *(int * const *)vb;
if (a[0] < b[0]) return -1;
if (a[0] > b[0]) return -1;
return (a[1] < b[1]) ? -1 : (a[1] > b[1]);

}

Five lines --- what'd I tell you?

HTH,
-Arthur

wow wow wow, thanks

 

[Ben Pfaff]

int compare( const void *va, const void *vb ) {
int *a = va;
int *b = vb;
printf("arg1 %d, %d\n", a[0], a[1]);
printf("arg2 %d, %d\n", b[0], b[1]);

if (a[0] > b[0]) {
return -1;
} else if (a[0] == b[0]) {
return (a[1] > b[1]) ? -1 : (a[0] < b[0]);
} else return 1;
}

I always find this kind of thing most easily readable when I
write it like this:

if (a[0] != b[0])
return a[0] > b[0] ? 1 : -1;
else if (a[1] != b[1])
return a[1] > b[1] ? 1 : -1;
else
return 0;

although in this case I'd be tempted to use a for loop:

for (i = 0; i < 2; i++)
if (a != b)
return a > b ? 1 : -1;
return 0;

 

[CBFalconer]

.... snip ...

int compare(const void *va, const void *vb)
{
int *a = *(int * const *)va;
int *b = *(int * const *)vb;
if (a[0] < b[0]) return -1;
if (a[0] > b[0]) return -1;
return (a[1] < b[1]) ? -1 : (a[1] > b[1]);
}

How about:

int compare(const void *va, const void *vb) {
const int *a = va;
const int *b = vb;

if (*a == *b) {
a++; b++;
}
return (*a > *b) - (*b > *a);
}

No casts. Single exit.

 

[beagle197]

why use const int ** assignment better? i assume 'const' keyword helps
compile time optimizations?

as for heap, i cleared that confusion after reading this article
http://www.cs.ucla.edu/~kohler/z/memoryallocationinc.html

funny at the time to read.

thanks

int compare( const void *arg1, const void *arg2 ) {
printf("arg1 %d, %d\n", ((int *) arg1)[0], ((int *) arg1)[1]);
printf("arg2 %d, %d\n", ((int *) arg2)[0], ((int *) arg2)[1]);
fflush(stdout);

if (((int *) arg1)[0] > ((int *) arg2)[0]) {

You're trying to treat these arguments as if they point to ints.
They don't. They point to int *s. Thus, you should be casting
them to int ** or, better yet, assigning them to a variable of
type "const int **".

return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
[...]

/* Sort remaining args using Quicksort algorithm: */
qsort( (void *)x, 6, sizeof( x[0] ), compare );

qsort isn't necessarily implemented as a quicksort.

The cast here should be unnecessary.

[...]

/* listing 2: using heap store */

I don't see any use of malloc in this version. Usually that's
what programmers mean when they say "heap".
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p\
);}return 0;}

 

[beagle197]

I used your template, need descending sort order, and finally this
worked. ("puts on cool looking sunglasses and goes outside")

Thanks

int compare(const void *va, const void *vb) {
int *a = *(int * const *)va;
int *b = *(int * const *)vb;

if (a[0] < b[0]) return 1;
if (a[0] > b[0]) return -1;
return (a[1] < b[1]) ? 1 : (a[1] > b[1]) ? -1 : 0;
}

Attempting to q-sort an array of int pairs, e.g. {{0,1}, {0, 0}, ...}
allocated using malloc/calloc, but the arguments I'm passing to qsort
are producing the incorrect results (see listing 1). Works for auto
object duration (e.g. heap) as in listing 2. Any ideas?

First guess, without even looking at the code: You'll be trying to
treat int[2] as if it were int*, or vice versa. Let's see if I'm right...

/* listing 1 : using malloc/calloc */

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

int compare( const void *arg1, const void *arg2 ) {
printf("arg1 %d, %d\n", ((int *) arg1)[0], ((int *) arg1)[1]);
printf("arg2 %d, %d\n", ((int *) arg2)[0], ((int *) arg2)[1]);
fflush(stdout);

if (((int *) arg1)[0] > ((int *) arg2)[0]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
if (((int *) arg1)[1] > ((int *) arg2)[1]) {
return -1;
} else if (((int *) arg1)[0] == ((int *) arg2)[0]) {
return 0;
} else if (((int *) arg1)[0] < ((int *) arg2)[0]) {
return 1;
}
} else
return 1;
}

Aaugh! Blecch! Ick! You shouldn't have any casts in your code, and
a straightforward comparison like this should be maybe five lines long,
at most. Here's something equivalent to what you wrote:

int compare( const void *va, const void *vb ) {
int *a = va;
int *b = vb;
printf("arg1 %d, %d\n", a[0], a[1]);
printf("arg2 %d, %d\n", b[0], b[1]);

if (a[0] > b[0]) {
return -1;
} else if (a[0] == b[0]) {
return (a[1] > b[1]) ? -1 : (a[0] < b[0]);
} else return 1;
}

Now, I notice two things: First, you have a couple of typos; you
write a[0] (or rather, ((int *)arg1)[0]) where you mean a[1] (or
rather, ((int *)arg1)[1]). So my code isn't really doing quite the
same thing as yours, because I'm not invoking undefined behavior
by falling off the end of the function without returning a value.

If you had compiled your code with warnings turned on ("gcc -W -Wall"),
you would have found this error at once.

The other thing I notice is that you're treating the input
arguments as if they were pointers to int, which is not the case ---
or if it is, then you're comparing different elements of the sorted
array, which isn't kosher at all. Let's see which is the case...

int main(int argc, char *argv[]) {
int i;
int **x;

x = malloc(6 * sizeof(int *));

x = malloc(6 * sizeof *x);

for (i = 0; i < 6; ++i) {
x = calloc(2, sizeof(int));

x = malloc(2 * sizeof *x);
'calloc' is only useful if you need the memory zeroed for some reason.
Since you immediately assign new values into it, you don't need it to
be zeroed.

/* assignments */
[snip]

for (i = 0; i < 6; ++i)
printf("%d, %d\n", x[0], x[1]);
printf("\n");
fflush(stdout);

You don't need to 'fflush' an output stream if you've just written a
newline to it; the newline flushes the stream by itself already.

/* Sort remaining args using Quicksort algorithm: */
qsort( (void *)x, 6, sizeof( x[0] ), compare );

qsort(x, 6, sizeof *x, compare);

...And here's the problem, exactly as I thought at first. You're trying
to qsort an array of 'int*', but your comparison function is written
(almost) as if you're trying to sort an array of 'int[2]'.

The comparison function for 'qsort' should be written this way, in
order to sort an array of T:

int compare(const void *va, const void *vb)
{
const T *a = va;
const T *b = vb;
return (*a < *b) ? -1 : (*a > *b);

}

Or if T is a small type, such as your int*:

int compare(const void *va, const void *vb)
{
T a = *(const T *)va;
T b = *(const T *)vb;
return (a < b) ? -1 : (a > b);

}

Therefore, what you wanted was:

int compare(const void *va, const void *vb)
{
int *a = *(int * const *)va;
int *b = *(int * const *)vb;
if (a[0] < b[0]) return -1;
if (a[0] > b[0]) return -1;
return (a[1] < b[1]) ? -1 : (a[1] > b[1]);

}

Five lines --- what'd I tell you?

HTH,
-Arthur