kevin.bagust said:
How about comparing the pointers rather than the items pointed to? So
something like this:
int compare( void *x, void *y )
int compare(const void *x, const void *y)
{
if ( x < y ) {
return -1;
}
else if ( y < x ) {
return 1;
}
else {
return 0;
}
}
Or...
#define UFO(x,y) (((y) < (x)) - ((x) < (y)))
int compare(const void *x, const void *y)
{
return UFO(x,y);
}
Trouble is, the standard states...
... The implementation may reorder elements of the array between
calls
to the comparison function, but shall not alter the contents of any
individual element.
There is nothing preventing qsort() from moving array elements in a
maner not determined by the comparison function, so long as the final
result meets the sort criteria.
Many sort implementations actually do this.[1]
AFAIK, it is not possible to make qsort() stable without encoding
original position information in the elements themselves, or having
the comparison function use a 'global' object recording pre-existing
positions.
[1]
% type stable.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define NELEM(x) (sizeof (x) / sizeof *(x))
int compare(const void *s, const void *t)
{
const char * const *u = s;
const char * const *v = t;
int cmp = strncmp(*u, *v, 3);
return cmp ? cmp : (u > v) - (u < v);
}
int main(void)
{
size_t i;
const char *array[] = { "aaa0", "aaa1", "aaa2", "aaa3", "aaa4",
"aaa5", "aaa6", "aaa7", "aaa8", "aaa9" };
fputs("before: ", stdout);
for (i = 0; i < NELEM(array); i++)
putchar(array
[3]);
putchar('\n');
qsort(array, NELEM(array), sizeof *array, compare);
fputs(" after: ", stdout);
for (i = 0; i < NELEM(array); i++)
putchar(array[3]);
putchar('\n');
return 0;
}
% gcc -ansi -pedantic stable.c
% a.exe
before: 0123456789
after: 5123406789
%
