mrgsrtl.pas

{ COMIENZO DE DESCRIPCION

Escribir un procedimiento
procedure MERGESORT(var L:lista); que ordena los elementos de una
lista usando el metodo de clasificacion por intercalacion. Es
decir, divide la lista en dos sublistas auxiliares L1 y L2 de
tamano similar, las ordena aplicando MERGESORT recursivamente y
luego intercala las sublistas: a) dividir L en dos sublistas L1, L2, 
b) clasificar L1 y L2 por MERGESORT , c) intercalar L1 y L2 en L. 
[Tomado 2do parcial de 2003, 3-Jun-2003]
Keywords: clasificacion, lista

FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $Id: mrgsrtl.pas,v 1.5 2003/07/05 02:04:23 mstorti Exp mstorti $}

program mrgsrtl_p;

uses u_listpi;

type
  lista	= listpi ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure MERGE_SORT(var L : lista) ;
var
   L1,L2 : lista;
   p,p1,p2 : posicion;
   band	 : integer;
   Lp	 : ^lista;
   c,x1,x2	 : integer;
begin
   { Inicializa listas auxiliares }
   L1.anula;
   L2.anula;
   p := L.primero;
   { band va cambiando de signo para indicar si}
   { tomamos de L1 o l2}
   band := 1;

   { Va poniendo uno en L1 y otro en L2 }
   c:=0;
   while p<>L.fin do
   begin
      if band=1 then
	 { Toma de lista L1 }
	 Lp := @L1
      else
	 { Toma de lista L2 }
	 Lp := @L2;
      band := -band;

      { Lp es un puntero a la lista correpondiente}
      { (puede ser L1 o L2) }
      { Saca el primero elemento de L y lo inserta en Lp }
      Lp^.inserta(L.recupera(L.primero),Lp^.primero);
      L.suprime(L.primero);
      { Contamos cuantos elementos hay. Si hay menos de tres }
      { entonces las listas L1 y L2 vana tener menos de 2 y}
      { no hace falta ordenar. }
      c:=c+1;
   end;

   if c>2 then
   begin
      { Ordena aplicando recursivamente }
      MERGE_SORT(L1);
      MERGE_SORT(L2);
   end;

   { Intercala. Va tomando el menor de los dos}
   { primeros elementos de L1 y L2 y lo inserta}
   { al fin de L }
   p1 := L1.primero;
   p2 := L2.primero;
   while (p1<>L1.fin) and (p2<>L2.fin) do
   begin
      x1 := L1.recupera(p1);
      x2 := L2.recupera(p2);
      if x1then
      begin
	 L.inserta(x1,L.fin);
	 L1.suprime(p1);
	 p1:=L1.primero;
      end
      else
      begin
	 L.inserta(x2,L.fin);
	 L2.suprime(p2);
	 p2:=L2.primero;
      end;
   end;

   { Pone todo el resto de L1 en L }
   while p1<>L1.fin do
   begin
      L.inserta(L1.recupera(p1),L.fin);
      L1.suprime(p1);
      p1 := L1.primero;
   end;

   { Pone todo el resto de L2 en L }
   while p2<>L2.fin do
   begin
      L.inserta(L2.recupera(p2),L.fin);
      L2.suprime(L2.primero);
      p2 := L2.primero;
   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 }
   MERGE_SORT(L);
   
   L.imprime('despues');
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}