vectores

Clasificación por mezcla Directa, con 2 Vectores:

Puede usarse un vector en lugar de dos fichero si se le considera como una secuencia con 2 extremos y se inspecciona de forma secuencial. En lugar de realizar la mezcla a partir de 2 ficheros, pueden tomarse artículos de ambos extremos del vector. De esta forma , el esquema general de la fase combinada de mezcla y división puede ilustrarse enla figura


Método de mezcla directa con dos vectores

El destino de los elementos mezclados se modifica déspues de cada par ordenado en la primera pasada, cada cuádruplo ordenado
en la segunda pasada, etc…, rellenando así alternativamente las dos secuencias de destino, representadas por ambos extremos
de un único vector. Después de cada pasada, ambos vectoresintercambian sus papeles; el de origen se convierte en el de destino, y viceversa.

Puede conseguirse una simplificación mayor uniendo en un solo
vector de tamaño doble los dos vectores simples conceptual-
mente distintos. Así los datos se representarán por

a:ARRAY[1..2n] of item
-Los índices i,j designan los dos ítems origen mientras k y l son
los índices destinos.
- Los datosiniciales son a1,….,an
-Up: variable booleana para designar la dirección del flujo
de datos.
-Cuando Up=true significa que en la pasada en curso los
componentes a1,….,an se moverán hacia las variables
an+1,….,a2n
-Cuando Up=false significa que en la pasada en curso los
componentes an+1,….,a2n se moverán hacia las variablesa1,….,an
-p: designa la longitud de las secuencias a combinar
(cada cuanto se realizan los agrupamientos).
-m: designa el número de ítems en las dos sucesiones que
quedan por mezclar.
-n: número de elementos a clasificar
-q y r: longitudes de las secuencias a mezclar
-h: indica el incremento de los índices (i,k) o decremento(j,l)

-simplificación:el destinosiempre se designa como k.
Tenemos el siguiente vector de tamaño 2n y visualizar paso a paso
el algoritmo:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
44
55
12
42
67
06
18
94








   
i j kl


PROCEDURE Mezcla Directa
VAR
i,j,k,l,t:index;
h,m,p,q,r:INTEGER; Up:BOOLEAN;
BEGIN
(*inicializar*)
Up:=true;
p:=1;
REPEAT
h:=1;
m:=n;/*m=8*/
/*Asigna indices según el flujo de datos*/
IF Up THEN
i:=1;j:=n;k:=n+1;l:=2n;
ELSE
k:=1;l:=n;i:=n+1;j:=2n;
END;
REPEAT { mezclarun tramo de i, j en k}
/*contempla el caso de que n no sea potencia de 2*/
IF 8>=1 THEN q=1 ELSE no se ejecuta END;
m:=m-q;/*m=7*/
IF 7>=1 THEN r=1 ELSE no se ejecuta END;
m:=m-r;/*m=6*/
WHILE (q#0) & (r#0) DO
IF a[i]0 DO
a[10]:=a[9]; k:=k+h; j:=8-1;/*j=7*/ r:=r-0;/*r=0*/
1 2 34 5 6 7 8 9 10 11 12 13 14 15 16

55
12
42
67
06
18

44
94






   
i j k l

WHILE q>0 DO
a[k]:=a[i]; k:=k+h ; i:=i+1; q:=q-1END;
h:=-h;/*h=-1*/
t:=k;/*t=n+3*/
k:=l;
l:=t;/*l=n+3*/
UNTIL m=0
(**************************************************)
(*la siguiente pasada de REPEAT*)
IF 6>=1 THEN q=1 ELSE no se ejecuta END;
m:=m-q;/*m=5*/
IF 5>=1 THEN r=1 ELSE no se ejecuta END;
m:=m-r;/*m=4*/
WHILE (q#0) & (r#0) DO
IF...