Seguimos buscando a Arshak. Ayudanos compartiendo!
Encuesta no oficial de docentes
Resultados de la encuesta no oficial de docentes
Probaste el SIGA Helper?

Donar $100 Donar $200 Donar $500 Donar mensualmente


Enviar respuesta 
 
Calificación:
  • 0 votos - 0 Media
  • 1
  • 2
  • 3
  • 4
  • 5
Buscar en el tema
[ALGORITMOS] Ordenar lista por otro campo
Autor Mensaje
oiga Sin conexión
Suspendido
Sin estado :(

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 13
Agradecimientos dados: 0
Agradecimientos: 0 en 0 posts
Registro en: Jul 2008
Mensaje: #1
[ALGORITMOS] Ordenar lista por otro campo Dudas y recomendaciones Algoritmos y Estructuras de Datos
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]
Otros adjuntos en este tema
.pdf  Dinamicas.pdf ( 37,59 KB / 134) por Mariano
17-07-2008 16:54
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Mariano Sin conexión
Empleado de Fotocopiadora
Sin estado :(
**

Ing. en Sistemas


Mensajes: 41
Agradecimientos dados: 0
Agradecimientos: 9 en 1 posts
Registro en: Apr 2008
Mensaje: #2
Re: [ALGORITMOS] Ordenar lista por otro campo
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 =)


Archivo(s) adjuntos
.pdf  Dinamicas.pdf (Tamaño: 37,59 KB / Descargas: 134)
17-07-2008 17:23
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Aye Sin conexión
Rock Admin
.
**********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 2.143
Agradecimientos dados: 69
Agradecimientos: 466 en 54 posts
Registro en: Mar 2008
Mensaje: #3
Re: [ALGORITMOS] Ordenar lista por otro campo
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.

[Imagen: digitalizartransparent.png]
17-07-2008 17:40
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
oiga Sin conexión
Suspendido
Sin estado :(

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 13
Agradecimientos dados: 0
Agradecimientos: 0 en 0 posts
Registro en: Jul 2008
Mensaje: #4
Re: [ALGORITMOS] Ordenar lista por otro campo
todo muy lindo pero alguien lo puede hacer?, porque yo lo postie porque no me sale. saludos.
20-07-2008 11:50
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
oiga Sin conexión
Suspendido
Sin estado :(

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 13
Agradecimientos dados: 0
Agradecimientos: 0 en 0 posts
Registro en: Jul 2008
Mensaje: #5
Re: [ALGORITMOS] Ordenar lista por otro campo
gracias
20-07-2008 21:07
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Aye Sin conexión
Rock Admin
.
**********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 2.143
Agradecimientos dados: 69
Agradecimientos: 466 en 54 posts
Registro en: Mar 2008
Mensaje: #6
Re: [ALGORITMOS] Ordenar lista por otro campo
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)

[Imagen: digitalizartransparent.png]
21-07-2008 01:10
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
oiga Sin conexión
Suspendido
Sin estado :(

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 13
Agradecimientos dados: 0
Agradecimientos: 0 en 0 posts
Registro en: Jul 2008
Mensaje: #7
Re: [ALGORITMOS] Ordenar lista por otro campo
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]
23-07-2008 14:21
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
pablo Sin conexión
ModdIng
Hombre de ingenio (?)
********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.637
Agradecimientos dados: 0
Agradecimientos: 24 en 14 posts
Registro en: Apr 2008
Mensaje: #8
Re: [ALGORITMOS] Ordenar lista por otro campo
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").
23-07-2008 14:45
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
oiga Sin conexión
Suspendido
Sin estado :(

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 13
Agradecimientos dados: 0
Agradecimientos: 0 en 0 posts
Registro en: Jul 2008
Mensaje: #9
Re: [ALGORITMOS] Ordenar lista por otro campo
hice otra lista porque no se me ocurre ordenar la misma lista por otro campo, y quiero ver si lo q hice esta bien
23-07-2008 15:52
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
pablo Sin conexión
ModdIng
Hombre de ingenio (?)
********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.637
Agradecimientos dados: 0
Agradecimientos: 24 en 14 posts
Registro en: Apr 2008
Mensaje: #10
Re: [ALGORITMOS] Ordenar lista por otro campo
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!
23-07-2008 17:04
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Aye Sin conexión
Rock Admin
.
**********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 2.143
Agradecimientos dados: 69
Agradecimientos: 466 en 54 posts
Registro en: Mar 2008
Mensaje: #11
Re: [ALGORITMOS] Ordenar lista por otro campo
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.

[Imagen: digitalizartransparent.png]
23-07-2008 17:15
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
pablo Sin conexión
ModdIng
Hombre de ingenio (?)
********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.637
Agradecimientos dados: 0
Agradecimientos: 24 en 14 posts
Registro en: Apr 2008
Mensaje: #12
Re: [ALGORITMOS] Ordenar lista por otro campo
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!
23-07-2008 23:51
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
leandrodg Sin conexión
Il Capo Cannoniere
Lost Admin
**********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 2.421
Agradecimientos dados: 11
Agradecimientos: 52 en 20 posts
Registro en: Mar 2008
Facebook Twitter YouTube
Mensaje: #13
Re: [ALGORITMOS] Ordenar lista por otro campo
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.

LeandroDG

Mi blog: http://www.logue.com.ar/blog
Ingeniero en Sistemas
24-07-2008 01:25
Visita su sitio web Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Aye Sin conexión
Rock Admin
.
**********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 2.143
Agradecimientos dados: 69
Agradecimientos: 466 en 54 posts
Registro en: Mar 2008
Mensaje: #14
Re: [ALGORITMOS] Ordenar lista por otro campo
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!

[Imagen: digitalizartransparent.png]
24-07-2008 08:28
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
pablo Sin conexión
ModdIng
Hombre de ingenio (?)
********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.637
Agradecimientos dados: 0
Agradecimientos: 24 en 14 posts
Registro en: Apr 2008
Mensaje: #15
Re: [ALGORITMOS] Ordenar lista por otro campo
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).
24-07-2008 10:59
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Buscar en el tema
Enviar respuesta 




Usuario(s) navegando en este tema: 1 invitado(s)