Ordenación de ficheros

Informática. Mezcla: natural y directa

  • Enviado por: El remitente no desea revelar su nombre
  • Idioma: castellano
  • País: España España
  • 12 páginas
publicidad

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