ORDENACION DE FICHEROS

MEZCLA DIRECTA

Se denomina Mezcla Directa al método más largo ya que es necesario mucho tiempo para la ordenación. La cantidad de números a comparar es muy extenso.

Con MEZCLA nos referimos a unir varios ficheros.

La definición o los pasos a seguir de dicho método es el que especificaremos a continuación:

Dividir el fichero inicial `a' en dos mitades e introducir los elementos en otros dos ficheros, `b' y `c', alternativamente.

Se mezclan `b' y'c' combinando elementos aislados para formar Pares ordenados al fichero `a', es decir, coger un elemento de `b' y otro de `c' ,ordenarlos entre sí e introducirlos en `a'.

Repetir los pasos 1 y 2, mezclando los pares ordenados para formar cuádruples ordenados.

Repetir los pasos anteriores, fundiendo cuádruples para formar óctuples... Se continúa duplicando cada vez el tamaño hasta que la secuencia total quede ordenada.

Con el siguiente ejemplo se verá con mayor claridad lo que hemos querido explicar anteriormente:

Teniendo el fichero `a':

a: 44 55 12 42 14 18 6 67 24 15 58 76 31

b ! 44 12 14 6 24 58 31 se divide en dos el

c ! 55 42 18 67 15 76 fichero `a'

a ! 44 55 12 42 14 18 6 67 15 24 58 76 31 Pares

ordenados

b ! 44 55 14 18 15 24 31 se divide por dobles

c ! 12 42 6 67 58 76

a ! 12 42 44 55 6 14 18 67 15 24 58 76 31

cuádruples ordenados

b ! 12 42 44 55 15 24 58 76

c ! 6 14 18 67 31

a ! 6 12 14 18 42 44 55 67 15 24 31 58 76

b ! 6 12 14 18 42 44 55 67

c ! 15 24 31 58 76

a ! 6 12 14 15 18 24 31 42 44 55 58 67 76

Para la ordenación de mayor número de elementos utilizaremos el siguiente programa:

Program mezcla_directa;

uses crt,dos;

type

fitx=file of integer;

var

f1,f2,f3:fitx;

h,h1,m,m1,s,s1,c,c1:word;

Procedure escribir_diferencia_en_segundos(h1,h,m1,m,s1,s,c1,c:word);

Var

aux,aux1,result:real;

Begin

aux1:=h1*3600+m1*60+s1+c1/1000;

aux:=h*3600+m*60+s+c/1000;

result:=aux1-aux;

writeln;

writeln ('Behar izan duen denbora segundutan:');

writeln(result);

end;

Procedure abrir_fitx (var f1,f2,f3:fitx);

var

izena:string[15];

begin

clrscr;

repeat

writeln ('Sartu ordenatu nahi duzun fitxategiaren izena: (fitxint.lis)');

readln (izena);

assign (f1,izena);

reset(f1);

until (not(eof(f1)));

assign (f2,'2.tmp');

assign (f3,'3.tmp');

end;

Procedure cerrar_fitx (var f1,f2,f3:fitx);

begin

close (f1);

close (f2);

close (f3);

erase (f3);

erase (f2);

end;

Procedure print (var f:fitx);

var

x:integer;

begin

reset(f);

while not(eof(f)) do

begin

read (f,x);

write (x, ' ');

end;

end;

Procedure copiar_elemento(var f1,destino:fitx; var fin_trama:boolean; var cont:integer);

var

x,siguiente:integer;

begin

if not(eof(f1)) then

begin

read (f1,x);

write (destino,x);

end;

fin_trama:=false;

cont:=cont-1;

if eof(f1) then fin_trama:=true

else if cont=0 then fin_trama:=true;

end;

Procedure copiar_trama (var f1,destino:fitx; i:integer);

var

fin_trama:boolean;

begin

repeat

copiar_elemento (f1,destino,fin_trama,i);

until fin_trama;

end;

Procedure mezcla_trama(var origen1,origen2,destino:fitx; i:integer);

var

r1,r2,otro1,otro2:integer;

fin_trama:boolean;

begin

otro1:=i;

otro2:=i;

repeat

if not(eof(origen1)) then

begin

read (origen1,r1);

seek (origen1,filepos(origen1)-1);

end;

if not(eof(origen2)) then

begin

read (origen2,r2);

seek (origen2,filepos(origen2)-1);

end;

if r1<r2 then

begin

copiar_elemento (origen1,destino,fin_trama,otro1);

if fin_trama then copiar_trama (origen2,destino,otro2);

end

else

begin

copiar_elemento (origen2,destino,fin_trama,otro2);

if fin_trama then copiar_trama (origen1,destino,otro1);

end

until fin_trama;

end;

Procedure mezclar(var f1,f2,f3:fitx; nt:integer);

begin

repeat

mezcla_trama (f2,f3,f1,nt);

until eof(f3);

if not(eof(f2)) then

begin

copiar_trama (f2,f1,nt);

end;

end;

Procedure distribuir (var f1,f2,f3:fitx; i:integer);

begin

repeat

copiar_trama (f1,f2,i);

if not(eof(f1)) then copiar_trama (f1,f3,i);

until eof(f1);

end;

Procedure ordenar_mezcla_directa (var f1,f2,f3:fitx;i:integer);

var

ra,aux:integer;

begin

repeat

if i=0 then i:=1

else i:=i*2;

rewrite (f2);

rewrite (f3);

reset(f1);

distribuir(f1,f2,f3,i);

reset(f2);

reset(f3);

rewrite(f1);

mezclar(f1,f2,f3,i);

until i>=filesize(f1);

end;

begin

abrir_fitx (f1,f2,f3);

gettime(h,m,s,c);

ordenar_mezcla_directa (f1,f2,f3,0);

gettime(h1,m1,s1,c1);

print(f1);

cerrar_fitx (f1,f3,f2);

escribir_diferencia_en_segundos(h1,h,m1,m,s1,s,c1,c);

readln;

end.

MEZCLA NATURAL

Con este método se aprovechan aquellos números que desde un principio están ordenados entre ellos, cosa que no se consideraba en el anterior caso, si no hubiera ningún elemento ordenado sería idéntico a la Mezcla Directa.

Teniendo en cuenta lo dicho definiremos:

TRAMA: secuencia ordenada.

En este caso los pasos a seguir son:

Mientras se cumpla ak < ak+1 se introducirán los elementos en el mismo fichero `b'.

Cuando se rompa la trama, es decir, ai-1 > ai se cambiará al otro fichero (`c') donde comenzará otra trama. Se irán introduciendo los números en este fichero hasta que la trama se vuelva a romper.

Se repetirán ambos pasos hasta que todos los elementos se hayan repartido en ambos ficheros.

Se mezclan `b' y `c' ordenando los elementos por tramas y se introducen en `a'.Es decir, la mezcla se realiza por medio de tramos ordenados.

Repetir pasos anteriores hasta que la secuencia total quede ordenada. Y el número de tramos sea 1.

b b a a a

c c

división de tramos mezcla de tramos hasta que el número

tramos sea 1

Como el caso anterior para mayor claridad de lo explicado haremos un pequeño ejemplo:

a: 17 31 5 59 13 42 43 67 11 23 29 47 3 7 71 2 19 57 37 61

Trama1: 17 31

Trama2: 5 59

Trama3: 13 41 43 67

Trama4: 11 23 29 47

Trama5: 3 7 71

Trama6: 2 19 57

Trama7: 37 61

b ! 17 31 13 41 43 67 3 7 71 37 61

c ! 5 59 11 23 29 47 2 19 57

a ! 5 17 31 59 11 13 23 29 41 43 47 67 2 3 7 19 57 71

37 61

b ! 5 17 31 59 2 37 19 57 71

c ! 11 13 23 29 41 43 47 67 37 61

a ! 5 11 13 17 23 29 31 41 43 47 59 67 2 3 7 19 37 61 71

b ! 5 11 13 17 23 29 31 41 43 47 59 67

c ! 2 3 7 19 37 61 71

a ! 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 59 61 67 71

Ordenado

Para ordenamientos de mayor envergadura utilizaremos el siguiente programa en el que aparte de ordenar los elementos calcularemos cuanto tiempo ahorramos respecto al método directo:

Program mezcla_natural;

Uses crt,dos;

Type

fitx=file of integer;

Var

fa,fb,fc:fitx;

h,h1,m,m1,s,s1,c,c1:word;

Procedure escribir_diferencia_en_segundos(h1,h,m1,m,s1,s,c1,c:word);

Var

aux,aux1,result:real;

Begin

aux1:=h1*3600+m1*60+s1+c1/1000;

aux:=h*3600+m*60+s+c/1000;

result:=aux1-aux;

writeln;

writeln ('Behar izan duen denbora segundutan:');

writeln(result);

end;

Procedure print (var f:fitx);

var

x:integer;

begin

reset(f);

while not(eof(f)) do

begin

read (f,x);

write (x, ' ');

end;

end;

Procedure abrir_fitx (var fa,fb,fc:fitx);

var

izena:string;

begin

clrscr;

repeat

write ('Sartu ordenatu nahi duzun fitxategiaren izena: ');

readln (izena);

assign (fa,izena);

reset (fa);

until (not(eof(fa)));

assign (fb,'b.tmp');

rewrite(fb);

assign (fc,'c.tmp');

rewrite(fc);

end;

Procedure cerrar_fitx (var fa,fb,fc:fitx);

begin

close (fa);

close(fb);

close(fc);

erase(fc);

erase(fb);

end;

Procedure copiar_elemento(var fa,destino:fitx;var fin_trama:boolean);

var

x,siguiente:integer;

begin

read (fa,x);

write (destino,x);

if eof(fa) then fin_trama:=true

else begin

read (fa,siguiente);

fin_trama:=(x>siguiente);

seek(fa,filepos(fa)-1);

end;

end;

Procedure copiar_trama (var fa,destino:fitx);

var

fin_trama:boolean;

begin

repeat

copiar_elemento (fa,destino,fin_trama);

until fin_trama;

end;

Procedure mezcla_trama(var origen1,origen2,destino:fitx);

var

r1,r2:integer;

fin_trama:boolean;

begin

repeat

read (origen1,r1);

seek(origen1,filepos(origen1)-1);

read (origen2,r2);

seek (origen2,filepos(origen2)-1);

if r1<r2 then

begin

copiar_elemento (origen1,destino,fin_trama);

if fin_trama then copiar_trama (origen2,destino);

end

else

begin

copiar_elemento (origen2,destino,fin_trama);

if fin_trama then copiar_trama (origen1,destino);

end

until fin_trama;

end;

Procedure mezclar(var fa,fb,fc:fitx;var nt:integer);

begin

repeat

mezcla_trama (fb,fc,fa);

nt:=nt+1;

until eof(fc);

if not(eof(fb)) then

begin

copiar_trama (fb,fa);

nt:=nt+1;

end;

end;

Procedure distribuir (var fa,fb,fc:fitx);

begin

repeat

copiar_trama (fa,fb);

if not(eof(fa)) then copiar_trama (fa,fc);

until eof(fa);

end;

Procedure ordenar_mezcla_natural (var fa,fb,fc:fitx);

var nt:integer;

begin

repeat

rewrite(fb);

rewrite(fc);

reset(fa);

Distribuir(fa,fb,fc);

reset(fb);

reset(fc);

rewrite(fa);

nt:=0;

mezclar(fa,fb,fc,nt);

until nt=1

end;

begin

abrir_fitx (fa,fb,fc);

gettime(h,m,s,c);

ordenar_mezcla_natural (fa,fb,fc);

gettime(h1,m1,s1,c1);

print(fa);

escribir_diferencia_en_segundos(h1,h,m1,m,s1,s,c1,c);

readln;

cerrar_fitx (fa,fc,fb);

end.

Para el correcto funcionamiento de los anteriores programas deberemos introducir otro programa que nos indique el número de elementos para la ordenación , nombrar el fichero ,es decir, que cree el fichero `a'.El programa utilizado para ello es el siguiente:

Program fitx_Zenb;

Var

f:file of integer;

i,x:integer;

fitx_izen:string;

Begin

writeln ('Idatzi fitxategiaren izena:');

readln(fitx_izen);

assign (f,fitx_izen);

rewrite (f);

randomize;

for i:=1 to 2000 do

begin

x:=random(3000);

write (f,x);

end;

close(f);

end.

12