[ Foro de Pascal ]

Ordenar elementos de una lista

21-Nov-2015 20:12
Invitado (Mateo)
10 Respuestas

buenas, tengo que entregar una tarea el lunes y me he trancado con el ultimo procedimiento, es hacer una lista ordenada por aproximación, y en caso que sea igual, ordenar por turno...

 
function ListaOrdenada(historia : THistoria) : ListaNotas;
 
	function InsertarElemento(historia: THistoria; r: ListaNotas; var i: integer): ListaNotas;
	var
		p,q			: ListaNotas;
		j,limite	: integer;
	begin
		InsertarElemento:=r;
		new(p);
		limite:=historia.tope;
		for j:=1 to limite do
			p^.codigo:=historia.info[i].codigo;
			p^.buenos:=historia.info[i].buenos;
			p^.regulares:=historia.info[i].regulares;
			p^.turno:=i;
			p^.siguiente:=nil;
			inc(i);
				if r = nil then
					r:= p
				else 
					begin
						q:= r;
						while q^.siguiente <> nil do
							q:= q^.siguiente;
						q^.siguiente:= p;
					end;
			end; 
var 
	lista				: ListaNotas;
	i,k,limite		: integer;
 
begin
	{ aproximacion:= 10 * (buenos + regulares); }
	limite:=historia.tope;
	new(lista);
	if limite = 0 then	{lista vacia}
		lista := nil; 
	k:=1;	
	for i:=1 to limite do
 		InsertarElemento(historia,lista,k);
		inc(k);
 
	ListaOrdenada:=lista;
end;
 


tendria que quedar asi:
(lista vacia)Impresion de historia
---------------------
FBCD-->  buenos : 2 regulares : 0
CDBB-->  buenos : 1 regulares : 1
DEBE-->  buenos : 2 regulares : 1
DCEC-->  buenos : 2 regulares : 1
EEAB-->  buenos : 0 regulares : 3
-*-*-*-*-*-*-*-*-*-*-
Imprimir lista
--------------
EEAB -->  Bs = 0,  Rs = 3 ( turno: 5)
CDBB -->  Bs = 1,  Rs = 1 ( turno: 2)
FBCD -->  Bs = 2,  Rs = 0 ( turno: 1)
DEBE -->  Bs = 2,  Rs = 1 ( turno: 3)
DCEC -->  Bs = 2,  Rs = 1 ( turno: 4)


Gracias de antemano


21-Nov-2015 21:44
Nacho Cabanes (+31)

Por una parte, si no incluyes los tipos de datos THistoria ni ListaNotas, no se puede probar y es más difícil detectar errores. Lo ideal es que reduzcas tu programa al fragmento más pequeño que funciona pero falla.

Por otra parte, no entiendo la lógica que estás planteando: un "for" recorrerá todos los elementos para insertar al final, no en orden. Sería más razonable un "while". De hecho, el "if" que tienes del "for" debería ser lo primero. Y sí tienes un "while", pero que se comporta igual que el "for", avanzando hasta llegar al final de la lista (nil). ¿No deberías comparar con un cierto campo si quieres ordenar?


21-Nov-2015 22:00
Invitado (Mateo)

 

 
type
 
    RangoCodigo =  1..LARGO_CODIGO;
    RangoBR = 0 .. LARGO_CODIGO;
    TipoCodigo = array [RangoCodigo] of char;	
    TRegistroNota = record
		       codigo : TipoCodigo;
		       buenos,
		       regulares: RangoBR;
    end;
 
    THistoria  = record
		    info : array [1..MAXIMO_INTENTOS] of TRegistroNota;
		    tope : 0..MAXIMO_INTENTOS;
    end;
 
    ListaNotas = ^CeldaNota;
    CeldaNota = record
         codigo    : TipoCodigo;
         buenos    ,
         regulares : RangoBR;
         turno     : 1 .. MAXIMO_INTENTOS;
         siguiente : ListaNotas;
     end;
 


yo lo que hice en realidad fue insertar todos los elementos para luego ordenarlos, tal vez hay una manera mas fácil de insertarlos ya ordenados, es una serie de codigos con dos notas, buenos y regulares, y se tiene que ordenar en base a la nota, como esta ilustrado arriba.

lo que me da con el codigo que yo hice es:
(lista vacia)Impresion de historia
---------------------
FBCD-->  buenos : 2 regulares : 0
CDBB-->  buenos : 1 regulares : 1
DEBE-->  buenos : 2 regulares : 1
DCEC-->  buenos : 2 regulares : 1
EEAB-->  buenos : 0 regulares : 3
-*-*-*-*-*-*-*-*-*-*-
Imprimir lista
--------------
FBCD -->  Bs = 2,  Rs = 0 ( turno: 1)
CDBB -->  Bs = 1,  Rs = 1 ( turno: 2)
DEBE -->  Bs = 2,  Rs = 1 ( turno: 3)
DCEC -->  Bs = 2,  Rs = 1 ( turno: 4)
EEAB -->  Bs = 0,  Rs = 3 ( turno: 5)


21-Nov-2015 23:09
Invitado (Mateo)

Hola nacho, estoy con una nueva idea...

 
function EsApropiado(codigo : TipoCodigo; historia: THistoria): boolean;
var 
	i,j									: integer;
	buenos,regulares		: RangoBR;
begin
	{ Inicializo las variables }
	i:=1;
	j:=1;
	while (i <= historia.tope) and  (j <= historia.tope) do
		begin
			{ Comparo con el anterior guardado }
			ObtenerNota(historia.info[i].codigo,codigo,buenos,regulares);
		if (buenos = historia.info[i].buenos) and (regulares = historia.info[i].regulares) then
			{Segun la nota, se incrementa}
			inc(j);
		inc(i)
		end;
	{ Un codigo es apropiado si tiene la misma o mayor nota que el anterior }
	EsApropiado:= j > historia.tope
end;
 
function ListaOrdenada(historia : THistoria) : ListaNotas;
type 
				notas = array [0..10] of integer;	
 
				TAprox = record
						dato : array [1..100] of integer;
						tope : 0..5;
					end;
 
 
	function InsertarElemento(historia: THistoria; r: ListaNotas; var i: integer): ListaNotas;
	var
		p,q			: ListaNotas;
		j,limite	: integer;
	begin
		InsertarElemento:=r;
		new(p);
		limite:=historia.tope;
		 if r = nil then
			r:= p 
		else 
		begin
			q:= r; 
			 while q^.siguiente <> nil do
				 q:= q^.siguiente;  
			 q^.siguiente:= p; 
		end;
		for j:=1 to limite do
			p^.codigo:=historia.info[i].codigo;
			p^.buenos:=historia.info[i].buenos;
			p^.regulares:=historia.info[i].regulares;
			p^.turno:=i;
			p^.siguiente:=nil;
			inc(i);
	end;  
var 
	lista																: ListaNotas;
	i,j,limite														: integer;
	h,x,z,b,m,g													: integer;
	w,q,e,aux													: integer;
	aproximacion 											: TAprox;
	regulares,buenos										: notas;
 
begin
	limite:=historia.tope;
	w:=1; 
	aproximacion.tope:=0;
	new(lista);
 
	for b:=1 to limite do								{	CARGAR BUENOS Y REGULARES DE TODOS LOS CODIGOS	}
	begin
			buenos[w]:=historia.info[w].buenos;
			regulares[w]:=historia.info[w].regulares;
			inc(w);
		end;
																		{	INICIALIZO MI ARREGLO	}
	x:=1;
	for q:=1 to limite do
		aproximacion.dato[x]:=0;
 
 	if limite = 0 then										{	LISTA VACIA	}
		lista := nil;  
 
	e:=1;															{	CARGO APROXIMACION	}
	with aproximacion do
	begin
		for h:=1 to limite do 
		begin
			dato[e]:=(10*buenos[e]+regulares[e]);
			inc(e);
		end;
	end;
 
	b:=1;															{	ORDENO DE MAYOR A MENOR	}
	for j:=1 to limite-1 do
        for b:=j+1 to limite do 
		begin
		if (aproximacion.dato[j] > aproximacion.dato[b]) then
			begin
				aux:=aproximacion.dato[j];
				aproximacion.dato[j]:=aproximacion.dato[b];
				aproximacion.dato[b]:=aux;
			end;
		end; 
 
 
		{ for z:=1 to limite do
		InsertarElemento(historia,lista,i); }
 
	ListaOrdenada:=lista;
end;
 


tengo mis elementos ya ordenados, ahora solo me falta insertarlos en la lista, pero no he sido capaz de poder hacerlo...
Mi idea es, ir ingresando los datos segun mi orden ya establecido


21-Nov-2015 23:11
Invitado (Mateo)

Pero al intentar ingresar los elementos llamando a la funcion

 
for z:=1 to limite do
	InsertarElemento(historia,lista,aproximacion.dato[z]);
 


me da error de rango...


22-Nov-2015 14:05
Nacho Cabanes (+31)

Ordenar una lista usando burbuja, me parece poco adecuado, cuando, por la propia definición de una lista, cada dato se puede guardar en su posición correcta, simplemente no avanzando hasta el final, sino hasta encontrar un elemento mayor que el actual.

Mira este apartado del curso:

http://www.aprendeaprogramar.com/mod/resource/view.php?id=574

Ahí tienes como hacerlo con una lista que tiene un único dato numérico, pero las ideas son las mismas aunque los datos sean más complejos.


22-Nov-2015 19:50
Invitado (Franco)

Mi duda es la misma pero mas generalizada. Leí la información del enlace pero me confundo un poco. Habría manera de comparar el elemento antes de insertarlo? Supongo que serviría, compararlo con todos los de la lista y en caso de ser necesario mover los elementos de la lista para hacerle el lugar en la posición adecuada.


22-Nov-2015 23:49
Nacho Cabanes (+31)

Lo que propones es "antinatural".

Ten en cuenta que un "array" es un conjunto de datos, todos del mismo tipo y que se encuentran en posiciones contiguas de memoria. Por eso, no hay "huecos", e insertar un nuevo dato supone desplazar todos los que le siguen.

Por el contrario, en una lista los datos no tienen por qué estar ordenados en memoria, porque se les asigna espacio de manera independiente. Por ejemplo, puede que el primer dato esté en la posición de memoria 1.000, el segundo esté en la 1.200 y el tercero en la 1.140.  Los campos "siguiente" son los que dicen a qué posición de memoria hay que saltar para leer el siguiente dato. Por eso, no tiene sentido cambiar de posición todos los datos. Basta con buscar en qué posición quedaría (en la tercera, por ejemplo) cambiar el campo "siguiente" del dato anterior (del segundo) para enlazar con el nuevo dato, y hacer que el campo "siguiente" del nuevo dato enlace con el que antes era el tercer dato.


23-Nov-2015 00:03
Invitado (Mateo)

El problema es que la unica comparacion para poder hacer es aproximacion, que es una cuenta tal que (10*buenos + regulares), y es un dato aparte el cual hay que ir ingresando con respecto a ese dato... no creo que se entienda
pero yo tengo 5 codigos con distintos buenos y regulares, y es necesario calcular antes la aproximacion para ingresarlos, pero al querer adjuntar la respectiva aproximacion como un dato de ese codigo es complicadisimo...
Estuve leyendo y analizando el enlance y la verdad no le encuentro mucha relacion ya que mis elementos(codigo,buenos,regulares,turno) de por si estan ordenados por turno, pero yo no puedo ingresarlos por esa cuenta, por que no tengo valores para comparar. Mi unico valor a comparar como seria  
begin
       { Si no hemos llegado a su sitio }
       if nodoInicial^.dato < valor
estaria siendo aproximacion, pero no encuentro la manera de adjuntarlo con cada dato.


23-Nov-2015 02:43
Invitado (Franco)

No puedo hacer que los ordene tomando en cuenta dos criterios. Logre que con el primer criterio vea si va antes o despues del ultimo elemento en la lista. Lo que no me sale es colocarlo antes segun un segundo criterio.
Por ejemplo: si el valor de la lista es mayor al nuevo, coloco lel elemento en el lugar anterior.
             
El problema viene cuando los valores son iguales y hay que evaluar un segundo criterio, parece que no lo analizara.


23-Nov-2015 07:55
Invitado (Mateo)

Despues de pensarlo, y probar varias horas, quedó al fin!
Siemplente idealicé la guia del enlace

 
procedure InsertarElemento(historia: THistoria;	var r: ListaNotas;	i: integer);
		var
			p							: ListaNotas;
			buenos, regulares	: Tnota;
		begin
			{	Llamo al procedimiento cargado	}
			Orden(buenos,regulares);
			{	Analizo, ordeno y cargo mi lista	}
			{	Si hay lista	}
			if r <> nil then
			begin
				{	Si no está en su lugar	}
				if (10*(buenos[i])+regulares[i]) >= (10*(r^.buenos)+r^.regulares) then 
					{ 	Miro la siguiente posición de forma recursiva	}
					InsertarElemento(historia,r^.siguiente,i)
				else
					{	Si hay lista, y esta en su lugar	}
					begin
						{	Reservo memoria	}
						new(p);
						{	Cargo los datos	}
						p^.codigo:=historia.info[i].codigo;
						p^.buenos:=historia.info[i].buenos;
						p^.regulares:=historia.info[i].regulares;
						p^.turno:=i;
						{ Miro al siguiente	}
						p^.siguiente:=r;
						{	Reengancho nodos	}
						r:=p;
			 		end;
				end
			 {	Si no hay lista, la creo }	
			else 
			begin
				{	Reservo memoria	}
				new(p);
				{	Cargo los datos	}
				p^.codigo:=historia.info[i].codigo;
				p^.buenos:=historia.info[i].buenos;
				p^.regulares:=historia.info[i].regulares;
				p^.turno:=i;
				{	Siguiente nulo	}
				p^.siguiente:=nil;
				{	Reengancho nodos	}
				r:=p
			end;
		end;
y quedó!
 


Muchas gracias por tus respuestas






(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)