UTNianos

Versión completa: [ALGORITMOS] Ordenar lista por otro campo
Actualmente estas viendo una versión simplificada de nuestro contenido. Ver la versión completa con el formato correcto.
Páginas: 1 2
Hola, tengo este problema, tengo una lista ordenada por campo llamese alumnos que son las letras, de menor a mayor por apellido, y yo quiero ordenarla de mayor a menor por nota. Alguien podria ayudarme, gracias.
[Imagen: dibujoyl2.th.jpg]
Hola, mira, creo uqe la forma mas sencilla, es crea una lista auxiliar, usar la funcion EnlazaNodo, que te agrego en este pdf ya ocn los diagramas, donde adems hay un monton de funciones mas de dinamica.

Creas una lista auxiliar, enlazas los nodos ya creados! (no volves a crear nuevos nodos e ir liberando memoria, SIMPLEMENTE cambias a donde apuntan los punteros siguiente, y dps asignas a la lista original a lo q ue apunta la lista auxiliar, y le haces un dispose a lista aux ylisto!

Cualquier cosa que no se me haya entendido volvee a preguntar =)
Espero no mandarme Cagad*s... Yo lo que haría es lo siguiente....

primero, lo que necesitás es guardar la información del nodo anterior (ahora te comento como)...

en la lista que tenés vos, lo que yo haría sería, ir sacando nodos, y rehubicándolos en otra lista.

el primer nodo que sacás, diréctamente lo ponés en la lista (con un flag o algo así, en un if)... Para el segundo nodo que saques, y para todos los siguientes (tené en cuenta que los nodos que sacás van a ser de la lista vieja, la que tenés vos....) vas a tener que recorrer la lista nueva e ir preguntando (con un while(lista <> NIL), y adentro un if ..) si el campo nota del registro que saqué de la lista vieja es menor al campo nota del nodo de la lista nueva...

Cada vez que hagas un ciclo por cada nodo de la lista nueva, necesitás guardar el nodo anterior (lo que dije al principio)... Cosa de que si el if le da verdadero.... vas a insertar un nodo, poníendole a este nuevo nodo la dirección del puntero anterior (para que apunte al siguiente) y al puntero anterior, la dirección del nodo incertado...

Espero que se haya entendido, soy un desastre para explicar cosas por la internete... cualquier cosa después me paso con grafiquito y con el algoritmo.
todo muy lindo pero alguien lo puede hacer?, porque yo lo postie porque no me sale. saludos.
gracias
oiga, querés el algoritmo o el fuente? Ya lo habías pensado con lo que dijimos o no? tenés alguna base o sólo la lista?

un toque más de info, y te ayudamos.... (ayudar no es hacer por vos, igualmente =P)
volviendo al tema hice una lista de sublistas ordenada por DNI y quiero ordenarla por Nota, hice una lista nueva (Lista2) e inserte ordenado por nota, diganme si esta bien hecho el pase. Saludos.

[Imagen: ffffffm1.th.jpg]
Necesitás tener otra lista nueva para algo? Siempre que sea posible, te conviene ordenar la misma lista que tenés, ya que es más eficiente. Claro, si tenés que mantener la original, entonces seguramente te convenga crear una nueva ordenada por el nuevo criterio.

Para ordenar podés usar cualquier criterio que te hayan enseñado, aunque creo que en Algoritmos sólo se ve BubbleSort ("burbujeo").
hice otra lista porque no se me ocurre ordenar la misma lista por otro campo, y quiero ver si lo q hice esta bien
Es que ordenar la lista por otro campo es lo mismo que ordenar la lista por cualquier campo, sólo que a la hora de comparar que campo tiene que ser menor a otro, lo que compararías son las notas. Ya no te importarían los índices iniciales.

Cuando insertás un elemento en la lista, tenés que comparar con los existentes para ver donde lo acomodás, y comparás según la nota. Bueno, para ordenarlos es lo mismo, ordenás según la nota... agarrás cualquier algoritmo de ordenamiento y donde va la condición de ordenamiento ponés la comparación entre notas.

Lo que hiciste creo que está bien de todas formas.

Saludos!
lo que yo veo que hiciste (pablo y demases, corríjanme =P) es una lista "Lista2" exactamente igual a "Lista"... si lo que querías era repetir la lista, entonces lo que hiciste está bien. ahora, si lo que querés es ordenar por un campo, yo haría algo parecido a lo que te dije más arriba... Te pido perdón por no poder hacerlo ahora, me estoy yendo... vuelvo tipo 9 e intento armártelo.

Pablo... burbujeo acaso no lo podía aplicar en estructuras que sepa cuál es el fin, es decir... en las que sepa qué cantidad de posiciones ocupa? (como los arrays???) me entró la duda... se agradece si me respondés.
Aye escribió:lo que yo veo que hiciste (pablo y demases, corríjanme =P) es una lista "Lista2" exactamente igual a "Lista"... si lo que querías era repetir la lista, entonces lo que hiciste está bien. ahora, si lo que querés es ordenar por un campo, yo haría algo parecido a lo que te dije más arriba... Te pido perdón por no poder hacerlo ahora, me estoy yendo... vuelvo tipo 9 e intento armártelo.

Pablo... burbujeo acaso no lo podía aplicar en estructuras que sepa cuál es el fin, es decir... en las que sepa qué cantidad de posiciones ocupa? (como los arrays???) me entró la duda... se agradece si me respondés.

Aye, me había olvidado que en algoritmos no solemos aplicar este tipo de ordenamiento sobre listas, pero me resulta muy "tosco" generar una nueva lista.

En realidad no habría problema para aplicar Bubble Sort, ya que lo que se hace es recorrer la lista hasta llegar al final, siempre comparando de a pares (lo cual no es problemático ya que es cuestión de tomar el nodo actual y compararlo con el siguiente, lo cual no es problema en una lista). No conocés el tamaño de la lista, pero eso no es problema, ya que en vez de hacer un for hasta n-1 hacés un while ptr^.siguiente <> NIL (creo que se anotaba así). Después tenés que comparar siempre contra uno menos, por lo cual probablemente vayas a necesitar almacenar la cantidad de elementos de la lista al leerla por completo la primera vez, y después ir restandole uno.
Es verdad, es más complicado, y ahora que lo vuelvo a pensar, la eficiencia no varía tanto, ya que en realidad no se usa más memoria ni nada porque un nodo puede sacarse de la lista vieja e insertarse en una nueva, por lo cual sólo hay cambios de punteros, no memoria duplicada. Tampoco implica más recorridos de la lista que hacer un Bubble Sort.
A nivel práctico, y considerando la manera de Algoritmos, creo que estaría bien si usa una nueva lista, ya que no recuerdo que hayan dado una mejor forma de hacerlo.



(esto que sigue lo pongo a nivel informativo, pero no es relevante para lo que se ve en algoritmos... si les resulta delirante, pueden dejarlo =P)
Cualquier otra forma implicaría pensar un algoritmo de ordenamiento, por ejemplo, una opción sería:
* Busco el mínimo de toda la lista, y lo pongo como primer elemento.
* Busco el mínimo de la lista a partir del 2º elemento, y lo pongo como segundo elemento.
* Busco el mínimo de la lista a partir del 3º elemento, y lo pongo como tercer elemento.
...
Y así hasta que esté ordenada.

La cantidad de lecturas de nodos (considerando una lista de N nodos) que tendrían que hacer sería:

N (para el primer mínimo) + (N-1) (para el segundo mínimo) + (N-2) (para el primer mínimo) + ...

N + (N-1) + (N-2) + ... + 3 + 2 + 1

Esto era equivalente a N*(N-1)/2, que son la cantidad de lecturas necesarias, y casualmente es la misma cantidad de lecturas que requiere un ordenamiento de burbuja.
De forma un poco más complicada, se puede demostrar que leer toda la lista para sacar a cada elemento (N lecturas) y luego insertarlo en una lista nueva (recorrer 0 elementos, 1, 2,...,N-1) lleva, en promedio también, N*(N-1)/2, por lo cual la cantidad de lecturas es la misma, el espacio en memoria no se incrementa gravemente en ningún caso, así que por facilidad (o costumbre), convendría hacer la típica inserción en una nueva lista.

Saludos!
Ojo, si conservás la lista en el orden previo y en el nuevo hay que tener cuidado porque en algoritmos le RE prestaban atención a la cantidad de memoria. De hecho es LA dificultad de la materia lograr meter todo en el tamaño que te daban =P. Era lo más complicado, al menos "cuando yo era joven" =P.
Pablo, perdoná mi ignorancia =P .... Pero, vos pensás recorrer la lista tantas veces como elementos tenga, e ir sacándolos en orden? Eso es eficiente? digo, hacer una lectura de toda la lista (imaginate que la lista tiene 3245897364503945623455645687569032349056 nodos) cada vez que saques un nodo, para incertarlo en orden?....

Aunque, por cada nodo, siempre hay una lista que recorrer... si lo piensan como yo dije antes, mi planteo fue....

1) sacar de a uno los nodos de la lista .
2) recorrer la lista nueva, comparando el campo por el cual se quiera ordenar.
3) siempre guardar el valor del anterior en un auxiliar.
4) insertar el nodo en el lugar correspondiente.

Qué es más eficiente???la única diferencia que veo es que en lo que yo digo, no hace falta recorrer la lista2 completa, sólo hasta que se encuentre la posición (es decir, hasta que se encuentre entre que nodos tiene que estar en que saqué de la lista vieja).... y por otro lado, que la forma de Pablo no necesitaun auxiliar, que guarde el anterior...

Saludos!
Aye, por las cuentas que hice, la cantidad de pasos que tenès es la misma o muy aproximada: yo recorro la lista original y agrego de una al final del ultimo elemento ordenado, vos tomas un elemento de una, y recorres la nueva. Fijate que a mi cada vez me quedan menos en la original, y a vos tambièn, solo que yo tengo que recorrer la original (que tiene de N a 1 elementos), y vos tenès que recorrer la nueva (que tiene de 1 a N elementos).
Al final, terminan siendo aproximadamente N*(N+1)/2 pasos, (es con +, no con -, hoy me acordé =P).

Lean, no sé si entendí bien lo que decís, pero creo que el problema resuelto así no requeriría más memoria de estructuras, ya que en realidad no generás una estructura nueva, sólo vas reorganizando los nodos a partir de otro puntero inicial (o del mismo como tomé yo, pero es básicamente lo mismo, porque la primera lista la estás desarmando).
Páginas: 1 2
URLs de referencia