8.3 ALGORITMO DE BUSQUEDA HASH.

Existe un método que puede aumentar la velocidad de 
búsqueda donde los datos no necesitan estar ordenados y 
esencialmente es independiente del número n. Este método 
se conoce como transformación de claves o hashing. El 
hashing consiste en convertir el elemento almacenado 
(numérico o alfanumérico) en una dirección (índice) dentro 
del array.


 La idea general de usar la clave para determinar la dirección 
del registro es una excelente idea, pero se debe modificar de 
forma que no se desperdicie tanto espacio. Esta modificación 
se lleva a cabo mediante una función que transforma una 
clave en un índice de una tabla y que se denomina función 
de Randomización o Hash. Si H es una función hash y X es 
un elemento a almacenar, entonces H(X) es la función hash
del elemento y se corresponde con el índice donde se debe 
colocar X.



El método anterior tiene una deficiencia: suponer que dos 
elementos X e Y son tales que H(X) = H(Y). Entonces, cuando 
un el elemento X entra en la tabla, éste se inserta en la 
posición dada por su función Hash, H(X). Pero cuando al 
elemento Y le es asignado su posición donde va a ser 
insertado mediante la función hash, resulta que la posición 
que se obtiene es la misma que la del elemento X. Esta 
situación se denomina Randomización o Hashing con 
colisión o choque.


Una buena función Hash será aquella que minimice los 
choques o coincidencias, y que distribuya los elementos 
uniformemente a través del array. Esta es la razón por la que 
el tamaño del array debe ser un poco mayor que el número 
real de elementos a insertar, pues cuanto más grande sea el 
rango de la función de randomización, es menos probable que 
dos claves generen el mismo valor de asignación o hash, es 
decir, que se asigne una misma posición a más de un 
elemento.

Funciones Hash más usadas:

1. Hash de División:

Dado un diccionario D, se fija un número m >= |D| (m mayor o igual al tamaño del diccionario) y que sea primo no cercano a potencia de 2 o de 10. Siendo k la clave a buscar y h(k) la función hash, se tiene h(k)=k%m (Resto de la división k/m).

2. Hash de Multiplicación

Si por alguna razón, se necesita una tabla hash con tantos elementos o punteros como una potencia de 2 o de 10, será mejor usar una función hash de multiplicación, independiente del tamaño de la tabla. Se escoge un tamaño de tabla m >= |D| (m mayor o igual al tamaño del diccionario) y un cierto número irracional φ (normalmente se usa 1+5^(1/2)/2 o 1-5^(1/2)/2). De este modo se define h(k)= Suelo(m*Parte fraccionaria(k*φ))

8.2 Búsqueda dicotómica (binaria)

Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuyeexponencialmente el número de iteraciones necesarias.

Está altamente recomendado para buscar en arrays de gran tamaño. Por ejemplo, en uno conteniendo 50.000.000 elementos, realiza como máximo 26 comparaciones (en el peor de los casos).

Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del array que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del array que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el array.

A continuación se presenta el pseudocódigo del algoritmo, tomando como elemento inicial el elemento central del array.

Datos de entrada:
  vec: vector en el que se desea buscar el dato
  tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive.
  dato: elemento que se quiere buscar.

Variables
  centro: subíndice central del intervalo
  inf: límite inferior del intervalo
  sup: límite superior del intervalo

inf = 0
sup = tam-1

Mientras inf <= sup:
  centro = ((sup - inf) / 2) + inf // División entera: se trunca la fracción
  Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario:
   Si dato < vec[centro] entonces:
    sup = centro - 1
   En caso contrario:
    inf = centro + 1
Fin (Mientras)
Devolver Falso

Implementación recursiva en C++ ^{[cita requerida]}

#include <iostream>
#include <vector>

bool busqueda_dicotomica(const vector<int> &v, int principio, int fin, int &x){
    bool res;
    if(principio <= fin){
        int m = (principio + fin)/2;
        if(x < v[m]) res = busqueda_dicotomica(v, principio, m-1, x);
        else if(x > v[m]) res = busqueda_dicotomica(v, m+1, fin, x);
        else res = true;
    }else res = false;
    return res;
}
/*{Post: Si se encuentra devuelve true, sino false}*/

8.1 BUSQUEDA SECUENCIAL

BUSQUEDA SECUENCIAL EXTERNA
Se utiliza cuando el vector no está ordenado o no puede ser ordenado previamente. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del arreglo hasta encontrarlo, o hasta que se llegue al final. La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo.

La búsqueda de un elemento dentro de un array es una de las operaciones más importantes en el procesamiento de la información, y permite la recuperación de datos previamente almacenados. El tipo de búsqueda se puede clasificar como interna o externa, según el lugar en el que esté almacenada la información (en memoria o en dispositivos externos). Todos los algoritmos de búsqueda tienen dos finalidades:

- Determinar si el elemento buscado se encuentra en el conjunto en el que se busca.

- Si el elemento está en el conjunto, hallar la posición en la que se encuentra.

En este apartado nos centramos en la búsqueda interna. Como principales algoritmos de búsqueda en arrays tenemos la búsqueda secuencial, la binaria y la búsqueda utilizando tablas de hash.

Consiste en recorrer y examinar cada uno de los elementos del array hasta encontrar el o los elementos buscados, o hasta que se han mirado todos los elementos del array.

EJEMPLO

NOTA

En este ejemplo se debe ir primero a la opción mostrar, pues de esta manera el arreglo se cargara de los datos del archivo, de otra manera marcara que no se encuentra el dato buscado.

using System; 
using System.Collections.Generic; 
using System.ComponentModel; 
using System.Data; 
using System.Drawing; 
using System.Text; 
using System.Windows.Forms; 

namespace BusquedaSecuencialExterna 
{ 
    public partial class Principal : Form 
    { 
        public Principal() 
        { 
            InitializeComponent(); 
        } 

        private void cmdMostrar_Click(object sender, EventArgs e) 
        { 
            frmMostrar m = new frmMostrar(); 
            m.Show(); 
        } 

        private void cmdBuscar_Click(object sender, EventArgs e) 
        { 
            frmBuscar b = new frmBuscar(); 
            b.Show(); 
        } 

        private void cmdSalir_Click(object sender, EventArgs e) 
        { 
            Close(); 
        } 
    } 
} 

using System; 
using System.Collections.Generic; 
using System.ComponentModel; 
using System.Data; 
using System.Drawing; 
using System.Text; 
using System.Windows.Forms; 
using System.IO; 

namespace BusquedaSecuencialExterna 
{ 
    public partial class frmMostrar : Form 
    { 
        public frmMostrar() 
        { 
            InitializeComponent(); 
        } 
        
        //Este método despliega los valores almacenados en el archivo previamente creado 
        //Los valores se despliegan al cargar la forma 
        private void frmMostrar_Load(object sender, EventArgs e) 
        { 
            //variable que almacenara lo que se extraerá del archivo. 
            string res; 
            //Creación del objeto de la clase StreamReader que se encargara de leer 
            //el archivo cuya ubicación será en un fólder previamente creado en la 
            //carpeta donde se encuentra la clase program.cs 
            //**NOTA** 
            //La ubicación se escribe ../../Archivo/Informacion.txt, incluyendo la 
            //extensión del archivo, ejemplo Info.dat, Info.txt, etc. 
            StreamReader s = new StreamReader("../../Archivo/Informacion.txt");
            //Ciclo que se encargara de ir almacenando los datos del archivo 
            //(en este caso números) en un arreglo
            for (int c = 0; c < Program.tamano; c++) 
            { 
                res = s.ReadLine(); 
                //Línea especifica que se encarga de guardar la información en un arreglo 
                //Como los datos extraídos del archivo son de texto y se desea manipular 
                //la información como numéricos solo agregamos la parte "int.Parse(res)" 
                //para indicar que lo que queremos almacenar será transformado a valor entero. 
                Program.arreglo[c] = int.Parse(res); 
            } 

            //Ciclo que se encarga de desplegar la información del arreglo en un listbox. 
            for (int i = 0; i < Program.tamano; i++) 
                listBox1.Items.Add(Program.arreglo[i]); 
        } 

        private void cmdCerrar_Click(object sender, EventArgs e) 
        { 
            Close(); 
        } 
    } 
} 

using System; 
using System.Collections.Generic; 
using System.ComponentModel; 
using System.Data; 
using System.Drawing; 
using System.Text; 
using System.Windows.Forms; 

namespace BusquedaSecuencialExterna 
{ 
    public partial class frmBuscar : Form 
    { 
        public frmBuscar() 
        { 
            InitializeComponent(); 
        } 
        // método que contiene el código que realizara la búsqueda (secuencial) 
        int BusquedaSecuencial() 
        { 
            int i = 0; 
            // Se da entrada a la "clave" que es valor que se desea buscar. 
            Program.clave = int.Parse(txtBusqueda.Text); 
            while (i < Program.tamano) 
            { 
                if (Program.arreglo[i] == Program.clave) 
                    return i; 
                i = i + 1; 
            } 
            return -1; // No se encuentra en el arreglo 
        } 

        private void cmdBuscar_Click(object sender, EventArgs e) 
        { 
            try 
            { 
                // Creación de la variable que almacenara el resultado 
                int Res; 
                //llamada al método que realiza la búsqueda binaria y se le asigna a una 
                //variable. 
                Res = BusquedaSecuencial(); 
                //condición que determina si se encontró el elemento, de lo contrario, despliega 
                //un mensaje. 
                if (Res == -1) 
                    MessageBox.Show("No se encontró el elemento"); 
                //Despliegue del Resultado. 
                txtResultado.Text = Res.ToString(); 
                groupBox2.Visible = true; 
            }
            catch 
            { 
                MessageBox.Show("Ocurrió un error"); 
            } 
        } 

        private void cmdLimpiar_Click(object sender, EventArgs e) 
        { 
            txtBusqueda.Clear(); 
            txtResultado.Clear(); 
            txtBusqueda.Focus(); 
            groupBox2.Visible = false; 
        } 

        private void cmdCerrar_Click(object sender, EventArgs e) 
        { 
            Close(); 
        } 
    } 
} 

Al igual que en la ventana de Busqueda secuencial, después de presionar el botón de Buscar, aparecerá un groupbox el cual al principio se encuentra “invisible”, es decir se manipulo la propiedad Visible = false, y cuando se presiona el botón buscar se cambia la propiedad a Visible = true, para mostrar los resultados de la búsqueda.

NOTA: Esta ventana muestra el indice del elemento en el arreglo, es decir, que nos muestra en la posicion en la que se encuentra dentro del arreglo.

8 Metodos de busqueda

Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

La variante más simple del problema es la búsqueda de un número en un vector.

7.1.2 Mezcla Natural

Ordenación por el método de mezcla equilibrada

El método de ordenación por mezcla equilibrada, conocido tambien como natural, es una optimization del metodo de mezcla directa.

La idea central de este algoritmo consiste en realizar las particiones tomando secuencias ordenadas de máxima longitud en lugar de secuencias de tamaño fijo previamente determinadas. Luego se realiza la fusion de las secuencias ordenadas, en alternada, sobre dos archivos. Aplicando estas acciones en forma repetida se logrará el archivo original quede ordenado. Para la realization de este proceso de ordenación se necesitaran cuatro archivos. El archivo original F y tres archivos auxiliares a los que se denominara F1, F2 y F3. De estos archivos, dos serán considerados de entrada y dos de salida; esto, de manera alternada, con el objeto de realizar la fusion-partición. El proceso termina cuando en la realización de una fusion-partición el segundo archivo quede vacío.

Supongamos que se desea ordenar las claves del archivo F utilizando el método mezcla equilibrada.

F:    09    75    14    68    29    17    31    25    04   05    13    18    72   46    61

Los pasos que se realizan son:

PARTICIÓN  INICIAL

F2:    09    75'    29'    25'    46    61'
F3:    14    68'    17     31'    04   05    13    18    72'

PRIMERA FUSION-PARTICION

F:     09    14   68   75'    04   05    13    18    25    46    61    72'
F1:    17   29    31'

SEGUNDA FUSION-PARTICION

F1: 09 14 17 29 31 68 75'
F3: 04 05 13 18 25 46 61 72'

TERCERA FUSION-PARTICION

F:    04   05    09    13    14    17    18    25    29    31    46    61    68    72   75

Observe que al realizar la tercera fusion-partición el segundo archivo queda vacío; por lo tanto, se puede afirmar que el archivo ya se encuentra ordenado. A continuación se presenta la description formal del algoritmo de mezcla equilibrada.

Mezcla_equilibrada (F, F1, F2, F3)
El algoritmo ordena los elementos del archivo F por el metodo de mezcla equilibrada. Utiliza tres archivos auxiliares F1, F2 y F3 BAND es una variable de tipo booleano

1. Llamar al algoritmo Particion inicial con F, F2 y F3
2. Llamar al algoritmo Particion fusion con F1, F3, F y F1 
3. Hacer BAND <- FALSO
4. Mientras ((F1 ≠ VACIO) o (F3 ≠VACIO)) Repetir
         4.1. Si (BAND = VERDADERO)
                  entonces
                        Llamar al algoritmo Particion_fusion con F2, F3, F y F1
                        Hacer BAND <- FALSO
                  si no
                        Llamar al algoritmo Particion_fusion con F, F1,F2 y F3
                        Hacer BAND <- VERDADERO
         4.2. Fin del condicional del paso 4.1
5. Fin del ciclo del paso 4

El algoritmo requiere para su funcionamiento de dos algoritmos auxiliares, Particion_inicial yParticion_fusion, los cuales se presentan a continuation.

Particion_inicial (F, F2, F3)El algoritmo produce la particion inicial del archivo F en dos archivos auxiliares, F2 y F3 AUX y R son variables de tipo entero. BAND es una variable de tipo booleano

1. Abrir el archivo F para lectura.
2. Abrir los archivos F2 y F3 para escritura.
3. Leer R de F.
4. Escribir R en F2.
5. Hacer BAND <- VERDADERO y AUX <- R 
6. Mientras (no sea el fin de archivo de F) Repetir
          Leer R de F
           6.1 Si (R a AUX)
                   entonces
                           Hacer AUX <-R
                           6.1.1 Si (BAND = VERDADERO)
                                           entonces
                                                  Escribir R en F2
                                           si no
                                                  Escribir R en F3
                           6.1.2. Fin del condicional del paso 6.1.1 
                   si no
                           Hacer AUX <- R
                           6.1.3. Si (BAND = VERDADERO) entonces
                                             Escribir R en F3
                                             Hacer BAND <- FALSO
                                      si no
                                             Escribir R en F2 
                                             Hacer BAND <- VERDADERO
                           6.1.4. Fin del condicional del paso 6.1.3
                      6.2. Fin del condicional del paso 6.1
7. Fin del ciclo del paso 6
8. Cerrar los archivos F, F2 y F3

Particion_fusion (FA, FB, FC, FD)

El algoritmo produce la particion y la fusion de los archivos FA y FB, en los archivos FC y FD R1, R2 y AUX son variables de tipo entero. BANl, BAN2 y BAN3 son variables de tipo booleano

1. Abrir los archivos FA y FBpara lectura.
2. Abrir los archivos FC y FD para escritura.
3. Hacer BAN1 <- VERDADERO, BAN2 <- VERDADERO,
                BAN3 <- VERDADERO y AUX <- -32 768  {AUX se inicializa con un valor negativo alto} 
4. Mientras ((no sea el fin de archivo de FA) o (BANl = FALSO)) y ((no sea el fin de archivo de FB) o ((BAN2 = FALSO)) Repetir
                4.1. Si (BAN1 = VERDADERO) entonces 
                                Leer R1 de FA
                                Hacer BAN1 <- FALSO
                4.2. Fin del condicional del paso 4.1
                4.3  Si (BAN2 = VERDADERO) entonces 
                                Leer R2 de FB 
                                Hacer BAN2 <- FALSO
                4.4. Fin del condicional del paso 4.3
                4.5. Si (R1 < R2) entonces 
                                4.5.1. Si (R1 ≥ AUX) entonces
                                                4.5.1.1.  Sí(BAN3 = VERDADERO)
                                                                entonces
                                                                                Escribir R1 en FC
                                                                si no
                                                                                Escribir R1 en FD
                                                4.5.1.2. Fin del condicional del paso 4.5.1.1
                                                Hacer BAN1 <- VERDADERO y AUX <-  R1 
                                           si no
                                                4.5.1.3.Si (BAN3 = VERDADERO)
                                                                entonces
                                                                                Escribir R2 en FC 
                                                                                Hacer BAN3 <- FALSO
                                                                si no
                                                                                Escribir R2 en FD
                                                                                Hacer BAN3 <- VERDADERO
                                                  4.5.1.4 Fin del condicional del paso 4.5.1.3
                                                   Hacer BAN2 <- VERDADERO y AUX <- -32 768
                                4.5.2. Fin del condicional del paso 4.5.1
                           si no 
                                4.5.3 Si (R2 ≥ AUX)
                                                entonces 
                                                                4.5.3.1. Si (BAN3 = VERDADERO)
                                                                                entonces
                                                                                                Escribir R2 en FC
                                                                                si no 
                                                                                                Escribir R2 en FD 
                                                                4.5.3.2. Fin del condicional del paso 4.5.3.1
                                                                Hacer BAN2 <- VERDADERO y AUX <- R2
                                                Si no 
                                                                4.5.3.3. Si (BAN3 = VERDADERO)
                                                                                entonces
                                                                                                Escribir R1 en FC
                                                                                                Hacer BAN3 <- FALSO
                                                                                si no
                                                                                                Escribir  R1 en FD
                                                                               Hacer BAN3 <- VERDADERO
                                                                4.5.3.4. Fin del condicional del paso 4.5.3.3
                                                                Hacer BAN1 <- VERDADERO y AUX <- -32 768
                                4.5.4. Fin del condicional del paso 4.5.3
                4.6. Fin del condicional del paso 4.5
5. Fin del ciclo del paso 4
6. Si (BAN1 = FALSO) entonces 
                6.1. Si (BAN3 = VERDADERO)
                                entonces
                                                Escribir R1 en FC
                                                6.1.1. Mientras (no sea el fin de archivo de FA) Repetir 
                                                                Leer R1 de FA
                                                                Escribir R1 en FC
                                                6.1.2. Fin del ciclo del paso 6.1.1
                                si no
                                                Escribir R1 en FD
                                                6.1.3. Mientras (no sea el fin de archivo de FA) Repetir
                                                                Leer R1 de FA 
                                                                Escribir R1 en FD
                                                6.1.4.Fin del ciclo del paso 6.1.3 
                6.2. Fin del condicional del paso 6.1 
7. Fin del condicional del paso 6
8. Si (BAN2 = FALSO) entonces 
                8.1 Sí'(BAN3=VERDADERO)
                                entonces
                                Escribir R2 en FC 
                                8.1.1 Mientras (no sea el fin de archivo de FB) Repetir
                                                Leer R2 de FB
                                                Escribir R2 en FC 
                                8.1.2 Fin del ciclo del paso 8.1.1 
                        si no
                                Escribir R1 en FD
                                8.1.3. Mientras (no sea el fin de archivo de FB) Repetir
                                                Leer R2 de FB
                                                Escribir R2 en FD
                                8.1.4. Fin del ciclo del paso 8.1.3
                8.2. Fin del condicional del paso 8.1
9. Fin del condicional del paso 8
10.Cerrar los archivos FA, FB, FC y FD

Ejemplo en lenjuage C

void mezclaEquilibrada(int archf, int archf1, int archf2, int archf3){
    int archivo_vacio=ARCHIVO_NINGUNO;
    boolean band;
    particionInicial(archf, archf2, archf3);
    //imprimir("después de partición inicial");
    band = true;
    do{
        if(band){
            particionFusion(archf2, archf3, archf, archf1);
            //imprimir("después de partición fusión con band=true");
            band=false;
        }else{
            particionFusion(archf, archf1, archf2, archf3);
            //imprimir("después de partición fusión con band=false");
           band=true;
        }

        abrirL(archf1);
        if(fin(archf1)) archivo_vacio=ARCHIVO_F1;
        cerrar(archf1);

        if(archivo_vacio==ARCHIVO_NINGUNO){
           abrirL(archf3);
            if(fin(archf3)) archivo_vacio=ARCHIVO_F3;
            cerrar(archf3);
        }
    }while(archivo_vacio==ARCHIVO_NINGUNO);
    imprimir("al final");
    printf("el archivo que está vacío es: %d\nEl listado final está en el: %d\n",
    archivo_vacio, archivo_vacio-1);
}

void particionInicial(int archf, int archf2, int archf3){

    registro aux, r;
    /* Si band==true, el último registro se escribió en f2,
    * sino, fue en f3
    */
    boolean band;

    abrirL(archf);
    abrirE(archf2);
    abrirE(archf3);

    if(!leer(archf, &r)){
        printf("Archivo vacío\n");
        cerrar(archf);
        cerrar(archf2);
        cerrar(archf3);
        exit(0);
    }
    escribir(archf2,r);
    band=true;
    aux=r;
    while(!fin(archf)){
        leer(archf, &r);
        if(r>=aux){
            aux=r;
            if(band){
                escribir(archf2,r);
            }else{
            escribir(archf3,r);
        }
        }else{
            aux=r;
            if(band){
               escribir(archf3,r);
                band=false;
            }else{
              escribir(archf2,r);
              band=true;
          }
       }
    }

    cerrar(archf);
    cerrar(archf2);
    cerrar(archf3);
}

void particionFusion(int archfa, int archfb, int archfc, int archfd){
    registro aux, r1, r2;
   boolean band, dele1, dele2;

    abrirL(archfa);
    abrirL(archfb);
    abrirE(archfc);
    abrirE(archfd);

    band = true;
    leer(archfa, &r1);
    leer(archfb, &r2);
    if(r1<=r2)
        aux = r1;
    else
        aux = r2;
    dele1 = dele2 = false;
    while((!fin(archfa) || dele1!=true) && (!fin(archfb) || dele2!=true)){
        if(dele1){
           leer(archfa, &r1);
           dele1=false;
        }
        if(dele2){
            leer(archfb, &r2);
            dele2=false;
        }
        if(r1<r2){
           if(r1>=aux){
                //printf("probando... aux %d, r1 %d, r2 %d\n", aux, r1, r2);
                ayuda1(&aux, r1, archfc, archfd, band);
                dele1=true;
            }
            else if(r2>=aux){
            //printf("probando... r1 %d, aux %d, r2 %d\n", r1, aux, r2);
                ayuda1(&aux, r2, archfc, archfd, band);
                dele2=true;
            }
           else{
                //printf("probando... r1 %d, r2 %d, aux %d\n", r1, r2, aux);
                ayuda2(&aux, r1, archfc, archfd, &band);
                dele1 = true;
            }
        }
        else{
            if(r2>=aux){
            //printf("probando... aux %d, r2 %d, r1 %d\n", aux, r2, r1);
                ayuda1(&aux, r2, archfc, archfd, band);
                dele2=true;
            }
            else if(r1>=aux){
            //printf("probando... r2 %d, aux %d, r1 %d\n", r2, aux, r1);
                ayuda1(&aux, r1, archfc, archfd, band);
                dele1=true;
            }
            else{
            //printf("probando... r2 %d, r1 %d, aux %d\n", r2, r1, aux);
                ayuda2(&aux, r2, archfc, archfd, &band);
                dele2 = true;
            }
        }
    } //fin del while
    if(dele1 && fin(archfa))
    ayuda3(&aux, r2, archfb, archfc, archfd, &band);
    if(dele2 && fin(archfb))
    ayuda3(&aux, r1, archfa, archfc, archfd, &band);

    cerrar(archfa);
    cerrar(archfb);
    cerrar(archfc);
    cerrar(archfd);
}

7.1.1 Intercalacion Directa

Ordenación por mezcla directa

El metodo de ordenacion por mezcla directa es probablemente el más utilizado por su facil comprension. La idea central de este algoritmo consiste en la realization sucesiva de una particion y una fusion que produce secuencias ordenadas de longitud cada vez mayor. En la primera pasada, la particion es de longitud 1 y la fusion o mezcla produce secuencias ordenadas de longitud 2. En la segunda pasada, la particion es de longitud 2 y la fusion o mezcla produce secuencias ordenadas de longitud 4. Este proceso se repite hasta que la longitud de la secuencia para la particion sea:
Parte entera ((n +l)/2).

Donde n representa el número de elementos del archivo original.

Ejemplo. Supongamos que se desea ordenar las claves del archivo F. Para realizar tal actividad se utilizan los archivos auxiliares a los que se les denominara F1 y F2.

F:    09    75    14    68    29    17    31    25    04    05    13    18    72   46    61

PRIMERA PASADA

Particion en secuencias de longitud 1.

F1:  09'    14'    29'    31'    04'    13'    72'    61'
F2:  75'    68'    17'    25'    05'    18'    46'

Fusión en secuencias de longitud 2.

F:    09    75'    14    68'    17    29'    25    31'    04    05'    13    18'    46    72'    61'

SEGUNDA PASADA

Partición en secuencias de longitud 2.

F1:    09    75'    17    29'    04   05'    46    72'
F2:    14    68'    25    31'    13   18'    61'

Fusión en secuencias de longitud 4.

F:    09    14    68    75'    17    25    29    31'    04    05    13    18'    46    61    72'

TERCERA PASADA

Particion en secuencias de longitud 4.

F1:    09    14    68    75'    04    05    13    18'
F2:    17    25    29    31'    46    61    72'

Fusión en secuencias de longitud 8.

F:    09    14    17    25    29    31    68    75'    04    05    13    18    46    61    72'

CUARTA PASADA

Particion en secuencias de longitud 8.

Fl:    09    14    17    25    29    31    68    75'
F2:    04    05    13    18    46    61    72'

Fusión en secuencias de longitud 16.

F:    04   05    09    13    14    17    18    25    29    31    46    61    68    72   75

A continuacion se presenta el algoritmo de ordenacion de archivos por el metodo de mezcla directa.

Mezcla_directa (F, Fl, F2, N)
El algoritmo ordena los elementos del archivo F por el metodo de mezcla directa. Utiliza archivos auxiliares F1 y F2. N es el número de elementos del archivo F PART es una variable de tipo entero.

1. Hacer PART <- 1
2. Mientras (PART < parte entera ((N + 1) / 2)) Repetir
           Llamar al algoritmo Particiona con F, F1, F2 y PART
           Llamar al algoritmo Fusiona con F, F1, F2 y PART
           Hacer PART <- PART * 2
3. Fin del ciclo del paso 2

Observe que el algoritmo requiere para su funcionamiento de dos algoritmos liares, los cuales se presentan a continuacion.

Particiona (F, Fl, F2, PART)
El algoritmo genera dos archivos auxiliares, Fl y F2, a partir del archivo F. PART es longitud de la partition que se va a realizar K, L y R son variables de tipo entero

1. Abrir el archivo F para lectura.
2. Abrir los archivos F1 y F2 para escritura.
3. Mientras (no sea el fin de archivo de F) Repetir
          Hacer K <- 0
3.1. Mientras ((K < PART) y (no sea el fin de archivo de F)) Repetir 
           Leer R de F 
           Escribir R en Fl
           Hacer K <- K + 1
3.2. {Fin del ciclo del paso 3.1}
Hacer L <- 0
3.3. Mientras ((L < PART) y (no sea el fin de archivo de F)) Repetir 
           Leer R de F
           Escribir R en F2
           Hacer L <- L + 1
3.4 Fin del ciclo del paso 3.3
4. Fin del ciclo del paso 3

Fusiona (F, Fl, F2, PART)
El algoritmo fusiona los archivos F1 y F2 en el archivo F. PART es la longitud de la partición que se realizo previamente R1, R2, K y L son variables de tipo entero. Bl y B2 son variables de tipo booleano

1. Abrir el archivo F para escritura.
2. Abrir los archivos F1 y F2 para lectura.
3. Hacer B1 <- VERDADERO y B2 <- VERDADERO
4. Si (no es el fin de archivo de Fl) entonces 
       Leer B1 de F1
       Hacer B1 <- FALSO
5. {Fin del condicional del paso 4}
6. Si (no es el fin de archivo de F2) entonces 
       Leer R1 de F2 Hacer B2 <- FALSO
7. Fin del condicional del paso 6
8. Mientras ((no sea el fin de archivo de Fl) o (Bl = FALSO)) y ((no sea el fin de archivo de F2) o (B2 = FALSO)) Repetir
        Hacer K <- 0 y L <- 0
        8.1. Mientras ((K < PART) y (Bl = FALSO)) y ((L < PART) y ((B2 = FALSO)) Repetir
                     8.1.1. Si (R1 ≤ R2)
                             entonces
                                      Escribir B1 en F
                                      Hacer B1 <- VERDADERO y K <- K +1
                                      8.1.1.1 Si (no es el fin de archivo de F1) entonces
                                                         Leer R1 de F1
                                                         Hacer B1 <- FALSO
                                      8.1.1.2. Fin del condicional del paso 8.1.1.1
                             si no
                                         Escribir R1 en F
                                         Hacer B2 <- VERDADERO  y L <-L+1
                                          8.1.1.3 Si (no es el fin de archivo de F2) entonces
                                                      Leer R2 de F2
                                                      Hacer B2 <- FALSO
                                          8.1.1.4. Fin del condicional del paso 8.1.1.3
                     8.1.2 Fin del condicional del paso 8.1.1
        8.2 {Fin del ciclo del paso 8.1}
        8.3. Mientras ((K < PART) y (Bl = FALSO)) Repetir
                        Escribir R1 en F
                        Hacer B1 <- VERDADERO y K  <- K +1
                        8.3.1. Si (no es el fin de archivo de F1) entonces
                                    Leer R1 de F1
                                    Hacer B1 <- FALSO
                       8.3.2 Fin del condicional del paso 8.3.1
        8.4. Fin del condicional del paso 8.3
        8.5. Mientras ((L < PART)  y  (B2 = FALSO)) Repetir 
                        Escribir R2 en F
                        Hacer B2 <- VERDADERO y L <- L + 1
                        8.5.1. Si (no es el fin de archivo de F2) entonces 
                                Leer R2 de F2
                                Hacer B2 <- FALSO
                       8.5.2 Fin del condicional del paso 8.5.1
       8.6. Fin del ciclo del paso 8.5
9. Fin del ciclo del paso 8
10. Si (B1 = FALSO) entonces
        Escribir R1 en F 
11. Fin del condicional del paso 10
12.  Si (B2 = FALSO) entonces
             Escribir R2 en F
13. Fin del condicional del paso 12
14. Mientras (no sea el fin de archivo de F1) Repetir
        Leer R1 de F1
        Escribir R1 en F
15. Fin del condicional del paso 14
16. Mientras (no sea el fin de archivo de F2) Repetir
        Leer R2 de F2
        Escribir R2 en F
17. Fin del ciclo del paso 16
18. Cerrar los archivos F, Fl y F2