Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: Elkabeson en 31 Octubre 2021, 01:38 am



Título: Usar qsort para guardar
Publicado por: Elkabeson en 31 Octubre 2021, 01:38 am
Buenas noches, espero y tenga un feliz resto del dia la persona que esta leyendo esto, tengo una gran duda, me gustaria saber como puedo guardar 2 array de manera que, sean uno solo, me explico.

Tengo lo siguiente:

Código:
char *colores[] = {
    "Negro",
    "Marron",
    "Rojo"
};

int code[] = { 123, 520, 178 };

Se como guardarlos alfabeticamente los colores, y por orden ascendente los numeros, pero no se como guardarlos conjuntamente.

Utilizo esto para los numeros que me quedan asi: 123, 178, 520.

Código:
// para intercambear
qsort(code, 3, sizeof(char *), funcion);

// La funcion
int int_a = * ( (int*) p1 );
    int int_b = * ( (int*) p2 );

    if ( int_a == int_b ) return 0;
    else if ( int_a < int_b ) return -1;
    else return 1;

Para los colores utilizo esto, y queda asi: marron, negro, rojo, en orden del alfabeto.

Código:
qsort(fun, 10, sizeof(char *), comprobante);

return strcmp(* (char * const *)a, * (char * const *)b);

Lo que quiero hacer es lo siguiente.

Ordenar mediante numero

123, negro
178, rojo
520, marron

Ordenar mediante color.

520, marron.
123 negro.
178, rojo

En pocas palabras que el que tiene al lado, se quede con el a la hora de ordenar una sola columna.

Por favor almenos un ejemplo de uno de ellos.


Título: Re: Usar qsort para guardar
Publicado por: MAFUS en 31 Octubre 2021, 02:47 am
Para hacerlo con qsort una forma rápida que veo sería hacer un struct con una pareja de datos de cada array y después hacer un array con ellos.

algo así:

Código:
struct par {
   int code;
   char color[10]
};

Despues generas un array de 3 pares con ese struct, metes los datos colores y code, cada uno en la posición que te interese, haces dos funciones de comparación para qsort, una que ordene por code y la otra por color y ya lo tienes.


Título: Re: Usar qsort para guardar
Publicado por: Elkabeson en 31 Octubre 2021, 03:04 am
Buenas, muchísimas gracias por responder !

Esta muy buena tu idea, gracias una vez mas !

Pero a mi me gustaría realizarlo sin crear alguna estructura, ejemplo usando array auxiliares, y realizando los ordenamientos sin tocar los datos originales.

Tengo la idea pero no se como realizarlo, aquí es donde estoy parado totalmente.


Título: Re: Usar qsort para guardar
Publicado por: Serapis en 31 Octubre 2021, 17:55 pm
Eso es ordenar varias columnas, típicamente suele ser preciso para el uso de controles tipo grid con múltiples columnas.

En general en esos caso conviene usar un algoritmo que sea estable, para que en el caso de que haya ítems con igual valor, permanezcan en el orden primigenio (uno respecto de otros que comparten esa igualdad de valor). Al caso quicksort no es estable, hay quien usa Mergesort, que sí lo es o en su defecto bubblesort, que también lo es, pero imagínate lo lentísimo que pueda ser cuando la cantidad de elementos crece...

Otra cuestión general es que dichos controles suelen tener en efecto una estructura, donde cada columna es representada por un campo en la estructura, con lo que en efecto al ordenar (tal como te comenta Mafus), quedan ordenadas todas las columnas al tiempo. La desventaja clara de este método, es que impide o mejor dicho complica, la posibilidad de añadido o inserción dinamica de columnas.
En estos casos (cuando se pretende que el número de columnas sea variable) se abandona la estructura en favor de un array para cada fila, donde cada elemento de la fila ya no es un campo de una estructura sino un ítem en el array. Luego acaba siendo un array de arrays, o bien un array bidimensional. Si es bidimensional cualquier cambio de tamaño (en algunas de las dos dimensiones), supone una caída en el rendimiento...

Cuando he realizado algún grid que deseaba que tuviera la característica de añadido y eliminación dinámica, suele ser necesario disponer en efecto de columnas (separadas), donde cada columna es un array independiente (representada con una clase por ejemplo), y precisamente el ordenamiento lo he realizado siempre con Quicksort.
Como Quicksort, no es estable y esta característica es deseable (si ordenas por una columna y luego por otras que retenga el orden previo para ítems que en la columna actual siendo ordenada tengan igual valor (sin importar si en la previa columna ordenada no sucedía esto)), pues se debe modificar ligeramente quicksort, para que el orden permita ser estable.



He aquí el pseudocódigo de una variación de quicksort, para que permita ordenar diferentes array ligados entre sí por su índice inicial y que además sean estables...
En realidad, el cambio en la funcion, son pocos:
1 - Se limita a añadir un parámetro más (un array de mismo tamaño).
2 - Declarar una variable temporal para el intercambio de valores de este array adicional y.
3 - Añadir una línea de código extra, para el intercambio, cuando dos items deban ser intercambiados de orden.
Es precisamente el array 'ixEstable', quien se encarga de ir manteniendo la coherencia del cambio de ubicación... donde fue a a parar cada item. El 'antes' tenía por valores precisamente su orden: 0,1,2,3,4... size-1, el 'después' viene reflejado a la salida que depende del desorden que tenía el array a ordenar..
Código:
funcion QuicksortEst(datos(), ixEstable(), min, max)
    entero j, k, Pivot, tmpD, tmpX
   
    j = Min: k = Max
    Pivot = Datos((j + k) \ 2)   //tomamos como pivot el valor en medio del rango entre min y max.
    hacer mientras  (j <= k)
        hacer mientras (Datos(j) < Pivot); j += 1; repetir
        hacer mientras (Datos(k) > Pivot); k -= 1; repetir
       
        si (j <= k)
            Si (j < k)
                // intercambia los datos. En realidad conviene el puntero al dato, para poder utilizar distintos tipos de datos en la función).
                // luego tmpd = datos(k), puede ser el puntero o el valor al elemento en datos(k)... entiéndase según necesidades.
                tmpD = Datos(k); Datos(k) = Datos(j); Datos(j) = tmpD   
                // con cada intercambio en el orden, intercambiamos los valores del array adicional, que nos ayudará a mantener la estabilidad.
                tmpX = IxEstable(k); IxEstable(k) = IxEstable(j); IxEstable(j) = tmpX
            fin si
            j += 1; k -= 1
        sino
            salir del bucle
        fin si
    Repetir
   
    si (Min < k) llamada a QuicksortEst(Datos, IxEstable, Min, k)
    si (Max > j) llamar a QuicksortEst(Datos, IxEstable, j, Max)
fin funcion


Eso sí para el resto de columnas, el orden está basado en el array adicional, luego cada array debe ser recorrido para establecer dicho nuevo orden, así el costo total de ordenar será la suma del QuickSort, + el recorrido para el intercambio para mantener la estabilidad en cada array.
Una función adicional, debe alojar la llamada a la función quicksort modificada que se ha puesto antes, aunque previamente a dicha llamada, debe establecer el valor al array 'ixEstable', y luego tras el orden reasocia el resto de arrays conforme al orden que mantiene este array 'orden'.

Dejo esta parte a tu ingenio... a ver si logras sacarlo, si pasado el tiemo no lo logras (no me refiero a 10 minutos, ni 4 horas) avisa, que te ponga un pseudocódigo para dicha función...

...dejo eso sí, una captura de muestra:
(http://imgfz.com/i/p0XSeGv.png)