Holas
Me está surgiendo un problema con la portabilidad del qsort, supongamos que
quiero ordenar un arreglo de estructuras...

struct mail{
char *autor;
char *tema;
};
......
struct mail A[50];
.......
entonces defino la siguiente función para la ordenación lexicográfica...

int comp_tema(const void *c1,const void *c2)
{
struct mail r1,r2;
r1=*(struct mail*)c1;
r2=*(struct mail*)c2;
return strcmp(r1.tema,r2.tema);
}

Ahora bien cuando aplico en una parte del código la ordenación del arreglo
de registros ...
qsort(Contener,cont,sizeof(struct mail),comp_tema);

en caso de empate... es decir que comp_tema devuelve cero, tenía el
prejuicio que ambas bibliotecas C ordenaban igual... pero no...

Es decir en linux sale...

a1 t1
a3 t1
a4 t1

en cambio en FreeBSD

a4 t1
a1 t1
a3 t1

Como el oreden es crítico en mi caso... que solución puedo implementar para
que esto no me suceda...

Saludos Horacio...

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

>>>>> "Horacio" == Horacio Castellini <hcaste***fonosur.com.ar> writes:

Horacio> Como el oreden es crítico en mi caso... que solución
Horacio> puedo implementar para que esto no me suceda...

Si son lexicograficamente iguales ¿cual es el orden "correcto"? Creo
que no existe una respuesta para ello.

Ahora bien, si el orden es critico para ti, usa algo extra (el otro
campos de la estructura, por ejemplo) para deshacer la ambiguedad.

Saludos. Iñaki.

- --
Get PGP/GPG Keys at http://www.escomposlinux.org/iarenaza/pgpkey.php
I use free software / Yo uso software libre
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)
Comment: Processed by Mailcrypt 3.5.8 <http://mailcrypt.sourceforge.net/>

iD8DBQFDmbWBZXLnGT1HLgcRAncmAJ9EukethKUmuMoKZSgnJu 3+CpSvKgCeK4LR
mERk94TVoIr/VcaCJ0yApyM=
=Vr4E
-----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

>>>>> "Horacio" == Horacio Castellini <hcaste***fonosur.com.ar> writes:

Horacio> Como el oreden es crítico en mi caso... que solución
Horacio> puedo implementar para que esto no me suceda...

Si son lexicograficamente iguales ¿cual es el orden "correcto"? Creo
que no existe una respuesta para ello.

Ahora bien, si el orden es critico para ti, usa algo extra (el otro
campos de la estructura, por ejemplo) para deshacer la ambiguedad.

Saludos. Iñaki.

- --
Get PGP/GPG Keys at http://www.escomposlinux.org/iarenaza/pgpkey.php
I use free software / Yo uso software libre
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)
Comment: Processed by Mailcrypt 3.5.8 <http://mailcrypt.sourceforge.net/>

iD8DBQFDmbWBZXLnGT1HLgcRAncmAJ9EukethKUmuMoKZSgnJu 3+CpSvKgCeK4LR
mERk94TVoIr/VcaCJ0yApyM=
=Vr4E
-----END PGP SIGNATURE-----

El Fri, 09 Dec 2005 11:08:17 -0300, Horacio Castellini
<hcaste***fonosur.com.ar> escribió:
>Holas
> Me está surgiendo un problema con la portabilidad del qsort, supongamos que
>quiero ordenar un arreglo de estructuras...
>
>en caso de empate... es decir que comp_tema devuelve cero, tenía el
>prejuicio que ambas bibliotecas C ordenaban igual... pero no...
>
>Es decir en linux sale...
>
>a1 t1
>a3 t1
>a4 t1
>
>en cambio en FreeBSD
>
>a4 t1
>a1 t1
>a3 t1
>
>Como el oreden es crítico en mi caso... que solución puedo implementar para
>que esto no me suceda...

El problema principal es como interpreta cada librería la igualdad.
Parece que Linux (como debe ser) en caso de igualdad de elementos no
los intercambia. Sin embargo parece que FreeBSD sí que hace ese
intercambio en caso de igualdad.

Una implementación en C podría ser:

void cambia (int *a, int *b) {
int t=*a;
*a=*b;
*b=t;
}

void __qsort (int arr[], int ini, int fin) {
if (fin > ini + 1) {
int piv = arr[ini], l = ini + 1, r = fin;
while (l < r) {
if (arr[l] <= piv) {
l++;
} else {
cambia (&arr[l], &arr[--r]);
}
}
cambia (&arr[--l], &arr[beg]);
__qsort (arr, ini, l);
__qsort (arr, r, fin);
}
}

Ese "if (arr[l] <= piv)" puede cambiarse por un "if (arr[l] < piv)"
sin que se modifique el resultado final (en cuanto al orden de
ordenación), pero hace que ciertos elementos del mismo valor quizá
sean comparados e intercambiados entre sí. Por supuesto esa
comparación realmente es el valor que devuelve la función que tú has
creado cuando se usa la función qsort de la librería de C.

Si de verdad deseas que el resultado sea exactamente igual te aconsejo
que ordenes por TODOS los campos de tu estructura sin dejarte ninguno
(a ser posible deja la clave primaria para el último lugar).

Es la única forma de garantizar la exactitud en la salida en cualquier
plataforma y usando cualquier método de ordenación.

Tú has puesto solo dos elementos en tu estructura, pero supongo que
tendrás aún más (no creo que se llame "mail" una estructura que no
contiene el correo electrónico de un autor .

Tanto Azdo como Eduardo te han dado soluciones más prácticas. Yo te
agrego que compares todos y cada uno de los elementos de tu estructura
(por supuesto por prioridades: por ejemplo... primero nombre, luego
primer apellido, luego segundo apellido, etc).

Un saludo.

--
Óscar Javier García Baudet
LinaresDigital
http://redstar.linaresdigital.com/

El Fri, 09 Dec 2005 11:08:17 -0300, Horacio Castellini
<hcaste***fonosur.com.ar> escribió:
>Holas
> Me está surgiendo un problema con la portabilidad del qsort, supongamos que
>quiero ordenar un arreglo de estructuras...
>
>en caso de empate... es decir que comp_tema devuelve cero, tenía el
>prejuicio que ambas bibliotecas C ordenaban igual... pero no...
>
>Es decir en linux sale...
>
>a1 t1
>a3 t1
>a4 t1
>
>en cambio en FreeBSD
>
>a4 t1
>a1 t1
>a3 t1
>
>Como el oreden es crítico en mi caso... que solución puedo implementar para
>que esto no me suceda...

El problema principal es como interpreta cada librería la igualdad.
Parece que Linux (como debe ser) en caso de igualdad de elementos no
los intercambia. Sin embargo parece que FreeBSD sí que hace ese
intercambio en caso de igualdad.

Una implementación en C podría ser:

void cambia (int *a, int *b) {
int t=*a;
*a=*b;
*b=t;
}

void __qsort (int arr[], int ini, int fin) {
if (fin > ini + 1) {
int piv = arr[ini], l = ini + 1, r = fin;
while (l < r) {
if (arr[l] <= piv) {
l++;
} else {
cambia (&arr[l], &arr[--r]);
}
}
cambia (&arr[--l], &arr[beg]);
__qsort (arr, ini, l);
__qsort (arr, r, fin);
}
}

Ese "if (arr[l] <= piv)" puede cambiarse por un "if (arr[l] < piv)"
sin que se modifique el resultado final (en cuanto al orden de
ordenación), pero hace que ciertos elementos del mismo valor quizá
sean comparados e intercambiados entre sí. Por supuesto esa
comparación realmente es el valor que devuelve la función que tú has
creado cuando se usa la función qsort de la librería de C.

Si de verdad deseas que el resultado sea exactamente igual te aconsejo
que ordenes por TODOS los campos de tu estructura sin dejarte ninguno
(a ser posible deja la clave primaria para el último lugar).

Es la única forma de garantizar la exactitud en la salida en cualquier
plataforma y usando cualquier método de ordenación.

Tú has puesto solo dos elementos en tu estructura, pero supongo que
tendrás aún más (no creo que se llame "mail" una estructura que no
contiene el correo electrónico de un autor .

Tanto Azdo como Eduardo te han dado soluciones más prácticas. Yo te
agrego que compares todos y cada uno de los elementos de tu estructura
(por supuesto por prioridades: por ejemplo... primero nombre, luego
primer apellido, luego segundo apellido, etc).

Un saludo.

--
Óscar Javier García Baudet
LinaresDigital
http://redstar.linaresdigital.com/

Horacio Castellini wrote:
> Holas
> Me está surgiendo un problema con la portabilidad del qsort, supongamos que
> quiero ordenar un arreglo de estructuras...
>
> struct mail{
> char *autor;
> char *tema;
> };
> ......
> struct mail A[50];
> .......
> entonces defino la siguiente función para la ordenación lexicográfica...
>
> int comp_tema(const void *c1,const void *c2)
> {
> struct mail r1,r2;
> r1=*(struct mail*)c1;
> r2=*(struct mail*)c2;
> return strcmp(r1.tema,r2.tema);

// no copies las estructuras
const struct mail *r1 = (const struct mail*)c1;
const struct mail *r2 = (const struct mail*)c2;
int ret;

if (!(ret=strcmp(r1->tema,r2->tema)))
ret = strcmp(r1->autor,r2->autor);

return ret;

> }
>
> Ahora bien cuando aplico en una parte del código la ordenación del arreglo
> de registros ...
> qsort(Contener,cont,sizeof(struct mail),comp_tema);
>
> en caso de empate... es decir que comp_tema devuelve cero, tenía el
> prejuicio que ambas bibliotecas C ordenaban igual... pero no...

No es problema de bibliotecas ni de plataformas, sino de tu función de
comparación. Según tu función 2 mails son iguales *SOLO* si tienen el
mismo tema, y el orden de los elementos iguales dependerá de la
implementación del algoritmo.

Vamos que si el algoritmo cree que 2 elementos son iguales pondrá
primero el que mejor le venga, ya que el orden entre esos elementos no
importa porque *TU* le has dicho que son iguales

> Es decir en linux sale...
>
> a1 t1
> a3 t1
> a4 t1
>
> en cambio en FreeBSD
>
> a4 t1
> a1 t1
> a3 t1
>
> Como el oreden es crítico en mi caso... que solución puedo implementar para
> que esto no me suceda...

Sólo estas comparando el campo tema. Deberías comparar también con autor
cuando los temas sean iguales.

> Saludos Horacio...

Saludos

Horacio Castellini wrote:
> Holas
> Me está surgiendo un problema con la portabilidad del qsort, supongamos que
> quiero ordenar un arreglo de estructuras...
>
> struct mail{
> char *autor;
> char *tema;
> };
> ......
> struct mail A[50];
> .......
> entonces defino la siguiente función para la ordenación lexicográfica...
>
> int comp_tema(const void *c1,const void *c2)
> {
> struct mail r1,r2;
> r1=*(struct mail*)c1;
> r2=*(struct mail*)c2;
> return strcmp(r1.tema,r2.tema);

// no copies las estructuras
const struct mail *r1 = (const struct mail*)c1;
const struct mail *r2 = (const struct mail*)c2;
int ret;

if (!(ret=strcmp(r1->tema,r2->tema)))
ret = strcmp(r1->autor,r2->autor);

return ret;

> }
>
> Ahora bien cuando aplico en una parte del código la ordenación del arreglo
> de registros ...
> qsort(Contener,cont,sizeof(struct mail),comp_tema);
>
> en caso de empate... es decir que comp_tema devuelve cero, tenía el
> prejuicio que ambas bibliotecas C ordenaban igual... pero no...

No es problema de bibliotecas ni de plataformas, sino de tu función de
comparación. Según tu función 2 mails son iguales *SOLO* si tienen el
mismo tema, y el orden de los elementos iguales dependerá de la
implementación del algoritmo.

Vamos que si el algoritmo cree que 2 elementos son iguales pondrá
primero el que mejor le venga, ya que el orden entre esos elementos no
importa porque *TU* le has dicho que son iguales

> Es decir en linux sale...
>
> a1 t1
> a3 t1
> a4 t1
>
> en cambio en FreeBSD
>
> a4 t1
> a1 t1
> a3 t1
>
> Como el oreden es crítico en mi caso... que solución puedo implementar para
> que esto no me suceda...

Sólo estas comparando el campo tema. Deberías comparar también con autor
cuando los temas sean iguales.

> Saludos Horacio...

Saludos

On 2005-12-09, Horacio Castellini <hcaste***fonosur.com.ar> wrote:
> Como el oreden es crítico en mi caso... que solución puedo implementar para
> que esto no me suceda...

Las implementaciones de qsort en linux y bsd son libres así que puedes
copiar la función de una y llevártela a la otra, por ejemplo llamándola
qsort2.

Pero la solución más fácil y lógica parece que pasa porque refines la
función de manera que nunca dé = (que para tí no tiene utilidad, sino
que es un estorbo). Por ejemplo usa el autor, como te dicen en otro
post, y después usa el resto de campos, el tamaño,...

Un saludo.
--claudio--

On 2005-12-09, Horacio Castellini <hcaste***fonosur.com.ar> wrote:
> Como el oreden es crítico en mi caso... que solución puedo implementar para
> que esto no me suceda...

Las implementaciones de qsort en linux y bsd son libres así que puedes
copiar la función de una y llevártela a la otra, por ejemplo llamándola
qsort2.

Pero la solución más fácil y lógica parece que pasa porque refines la
función de manera que nunca dé = (que para tí no tiene utilidad, sino
que es un estorbo). Por ejemplo usa el autor, como te dicen en otro
post, y después usa el resto de campos, el tamaño,...

Un saludo.
--claudio--

Horacio Castellini wrote:

> Holas
> Me está surgiendo un problema con la portabilidad del qsort,
> supongamos que
> quiero ordenar un arreglo de estructuras...
>
> struct mail{
> char *autor;
> char *tema;
> };
> .....
> struct mail A[50];
> ......
> entonces defino la siguiente función para la ordenación lexicográfica...
>
> int comp_tema(const void *c1,const void *c2)
> {
> struct mail r1,r2;
> r1=*(struct mail*)c1;
> r2=*(struct mail*)c2;
> return strcmp(r1.tema,r2.tema);
> }
>
> Ahora bien cuando aplico en una parte del código la ordenación del arreglo
> de registros ...
> qsort(Contener,cont,sizeof(struct mail),comp_tema);
>
> en caso de empate... es decir que comp_tema devuelve cero, tenÃ***a el
> prejuicio que ambas bibliotecas C ordenaban igual... pero no...
>
> Es decir en linux sale...
>
> a1 t1
> a3 t1
> a4 t1
>
> en cambio en FreeBSD
>
> a4 t1
> a1 t1
> a3 t1
>
> Como el oreden es crÃ***tico en mi caso... que solución puedo implementar
> para que esto no me suceda...
>
> Saludos Horacio...

¡Pues discrimÃ***nalo!

int comp_tema(const void *c1,const void *c2)
{
struct mail r1,r2;
int res;

r1=*(struct mail*)c1;
r2=*(struct mail*)c2;
if((res=strcmp(r1.tema,r2.tema))==0)
return strcmp(r1.autor,r2.autor);
else return res;
}