mrgsrtc.pas

{ COMIENZO DE DESCRIPCION

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

FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $Id: mrgsrtc.pas,v 1.2 2003/07/31 13:18:01 mstorti Exp mstorti $}

program mrgsrtl_p;

uses u_colapi;

type
  cola	= colapi ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure MERGE_SORT(var C : cola) ;
var
   C1,C2 : cola;
   band	 : integer;
   Cp	 : ^cola;
   cnt,x1,x2	 : integer;
begin
   { Inicializa colas auxiliares }
   C1.anula;
   C2.anula;
   { band va cambiando de signo para indicar si}
   { tomamos de C1 o l2}
   band := 1;

   { Va poniendo uno en C1 y otro en C2 }
   { Finalmente quedan ((n+1) div 2) en C1 y (n div 2) en C2 }
   cnt:=0;
   while not C.vacia do
   begin
      if band=1 then
	 { Toma de cola C1 }
	 Cp := @C1
      else
	 { Toma de cola C2 }
	 Cp := @C2;
      band := -band;

      { Cp es un puntero a la cola correpondiente}
      { (puede ser C1 o C2) }
      { Saca el primero elemento de C y lo inserta en Cp }
      Cp^.pone(C.frente);
      C.quita;
      { Contamos cuantos elementos hay. Si hay menos de tres }
      { entonces las colas C1 y C2 vana tener menos de 2 y}
      { no hace falta ordenar. }
      cnt:=cnt+1;
   end;

   if cnt>2 then
   begin
      { Ordena aplicando recursivamente }
      MERGE_SORT(C1);
      MERGE_SORT(C2);
   end;

   { Intercala. Va tomando el menor de los dos}
   { primeros elementos de C1 y C2 y lo inserta}
   { al fin de C }
   while (not C1.vacia) and (not C2.vacia) do
   begin
      x1 := C1.frente;
      x2 := C2.frente;
      if x1then
      begin
	 C.pone(x1);
	 C1.quita;
      end
      else
      begin
	 C.pone(x2);
	 C2.quita;
      end;
   end;

   { Pone todo el resto de C1 en C }
   while not C1.vacia do
   begin
      C.pone(C1.frente);
      C1.quita;
   end;

   { Pone todo el resto de C2 en C }
   while not C2.vacia do
   begin
      C.pone(C2.frente);
      C2.quita;
   end;
   
end;	 

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
   C : Cola;
   k,v : integer;
begin
   { genera una cola aleatoria }
   C.imprime('antes');
   C.anula;
   randomize;
   for k:=1 to 20 do
   begin
      v := random(40);
      write(v,' ');
      C.pone(v);
   end;
   writeln;

   { ordena }
   MERGE_SORT(C);
   
   C.imprime('despues');
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}