bubl.pas

{-<->-+-<->-+-<->-+-<->-+-<->-+-<->-+-<->-+-<->-+-<->-+-<->-
COMIENZO DE DESCRIPCION

Escribir un procedimiento procedure BURBUJA(var L:lista); que
ordena los elementos de una lista L mediante el metodo de
clasificacion por burbujas. Como en listas simplemente enlazadas no
es conveniente avanzar hacia el principio de la lista por una
cuestion de eficiencia, el algoritmo de burbuja se modifica de
manera de que los elementos mas grandes viajan hacia el fin.
[Tomado 2do Parcial de 2003, 3-Jun-2003]
Keywords: lista, clasificacion

FIN DE DESCRIPCION
$Id: bubl.pas,v 1.3 2003/07/31 13:52:49 mstorti Exp mstorti $
-<->-+-<->-+-<->-+-<->-+-<->-+-<->-+-<->-+-<->-+-<->-+-<->-} 
program bubble_p;

uses u_listpi;

type
  lista	= listpi ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure bubble(var L : lista) ;
var
   p,q	 : posicion;
   n,i,j,ep,eq : integer;
begin
   { Cuenta cuantos elementos `n' hay en L }
   n:=0;
   p := L.primero;
   while p<>L.fin do
   begin
      n := n+1;
      p := L.siguiente(p);
   end;

   { Va aplicando burbuja, pero desde adelante hacia atras}
   { ya que en listas enlazadas solo se puede avanzar}
   { (en forma eficiente) hacia atras }
   for j:=n downto 2 do
   begin
      p:=L.primero;
      for i:=1 to j-1 do
      begin
	 ep := L.recupera(p);
	 q:=L.siguiente(p);
	 eq := L.recupera(q);
	 if ep>eq then
	 begin
	    { Intercambia }
	    L.suprime(q);
	    L.inserta(eq,p);
	    p:=L.siguiente(p);
	 end
	 else
	    { Avanza }
	    p:=q;
     end;
   end;
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
   L : Lista;
   k : integer;
begin
   { genera una lista aleatoria }
   L.anula;
{    randomize; }
   for k:=1 to 20 do
      L.inserta(random(20),L.primero);
   L.imprime('antes');

   { ordena }
   bubble(L);
   
   L.imprime('despues');
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}