mrgsrt.pas

{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION

El algoritmo Mergesort modificado. El procedimiento Mergesort 
se basa en la estrategia "dividir para vencer". Primero se 
ordenan las posiciones impares entre si (recursivamente), 
luego las pares y, finalmente, se intercalan ambas 
subsecuencias. Si el intercalamiento se puede hacer en 
tiempo $O(n)$ entonces puede demostrarse que el n\'umero de 
operaciones total es $O(n log(n))$ en el peor caso. Ya hemos 
visto para la representaci\'on de conjuntos como listas
enlazadas clasificadas que el intercalamiento de dos listas 
enlazadas clasificadas se puede hacer en tiempo $O(n)$. 
Para vectores no es tan sencillo, y se conjetura que no se 
puede hacer tal operaci\'on en tiempo $O(n)$ sin uso de 
memoria adicional (es decir, no se puede hacer "in place"). 
Escriba un `procedure MERGEQ (var A:vector; N:tipo_elemento);' 
que ordena un vector cuyas posiciones pares e impares
est\'an ordenadas entre si, usando una cola auxiliar.  
[Tomado en el 3er parcial 2002 (25 de junio de 2002)]
keywords: clasificacion

FIN DE DESCRIPCION
}
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ Se propone el siguiente algoritmo de intercalaci\'on para 
vectores que utiliza una cola auxiliar $C$ (y por lo tanto 
no es "in place"). Por simplicidad asumimos que el n\'umero 
de elementos en el arreglo $n$ es par, que las posiciones 
impares y pares est\'an clasificadas entre si y que, 
inicialmente, la cola $C$ est\'a vacia. Considerando el 
arreglo $A$ de longitud $n=16$ de la figura, el algoritmo 
lo ordena en $n/2=8$ pasos. En cada paso el algoritmo ordena 
los elementos $p,q$ en las posiciones $2j-1$ y $2j$. 
Despu\'es del paso $j$ los primeros $2j$ elementos est\'an 
ordenados y ubicados en parte en la cabecera del vector 
(posiciones 1 a $k$, marcados en la figura con una caja 
rectangular) y en la cola $C$. Entre la posici\'on $k+1$ y 
la posici\'on $2j-1$ hay una serie de elementos (tantos como 
hay en $C$) cuyos valores son irrelevantes (en la figura 
est\'an marcados con una $X$).  El algoritmo es el siguiente
%
for j:=1 to n div 2 do begin
   p := A[2j-1]; q := A[2j]; r := min(p,q);
   poner max(p,q) en C;
   poner todos los elementos de C menores o iguales que r 
   en la cabecera de A (despues de la posicion k);
   poner r en la cabecera de A;
end;
poner todos los elementos restantes de C en la cabecera 
de A;

Se puede ver que el tama\~no de la cola es $O(\sqrt n )$, 
m\'as precisamente $\approx 0.82sqrt n$. }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{$ Id: mrgsrt.pas 2003/06/19 14:00:00 mstorti Exp jdelia  $ }
program mrgsrt_p;
uses u_colapi;
const N = 128;
type
   cola   = colapi;
   vector = array[1..N] of integer;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ Intercala dos secuencias en un vector comenzando en la 
posicion "com" y con intervalos "d". Las posiciones pares 
(es decir, "com+d", "com+3d", ...) estan ordenadas entre si.
Las posiciones impares tambien. Se utiliza una cola auxiliar}
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure merge (var         A: vector; 
                 var         C: cola; 
                     com, d, n: integer);
var
  i, k, aa, b, min, j : integer;
begin
  k := com;
  j := com;
{ pa(A,com,n,d); } { descomentar para ver como funciona }
  for i := 1 to n do begin
    aa := A [j];
  { Pone el maximo de `p,q' en la cola }
    b := A [j + d];
    if (aa < b) then begin
      min := aa;
      C.PONE (b); end
    else begin
      min := b;
      C.PONE (aa);
    end; {if}
    j := j + 2 * d;
    while (not C.VACIA) and (C.FRENTE < min) do begin
      A [k] := C.FRENTE;
      C.QUITA;
      k := k + d;
    end ; {while}
    A [k] := min;
    k := k+d;
  { pa (A,com,n,d); } { descomentar para ver como funciona }
   end; {i}
   while not C.VACIA do begin
     A [k] := C.FRENTE;
     C.QUITA;
     k := k + d;
   end; {while}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure pa (A: vector; com,n,d: integer);
var
  i, j : integer;
begin
  j := com;
  for i := 1 to n do begin
    write ( A[j],' ');
    j := j + d;
  end; {i}
  writeln;
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ Esta es una rutina auxiliar. Ordena "n" elementos de
un vector, desde la posicion "com" cada "d", es decir 
los elementos com, com+d, etc... Las posiciones pares y 
las impares ya estan ordenadas entre si. }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure MRGSRT1 (var         A: vector; 
                   var         C: cola; 
                       com, d, n: integer);
begin
   if (n > 1) then begin
      MRGSRT1 (A, C, com  , 2*d, n div 2);
      MRGSRT1 (A, C, com+d, 2*d, n div 2);
      MERGE   (A, C, com  ,   d, n div 2);
   end; {if}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ Este es un "wrapper" para evitar los argumentos "com" 
y "d". Define la cola auxiliar "C". }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure MRGSRT (var A :vector; n : integer);
var
  C : cola;
begin
  C.ANULA ;
  MRGSRT1 (A, C, 1, 1, n);
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
  A   : vector;
  j, M: integer;
begin
   M := 100; {inicialmente llenado con numeros aleatorios}
   randomize ;
   for j := 1 to N do begin
      A [j] := random (M);
   end;
   pa     (A,1,n,1); { Imprime vector }
   mrgsrt (A,N);     { Ordena  }
   pa     (A,1,n,1); { Imprime vector ordenado }
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}