Técnicas de Intercalación

La ordenación de datos por intercalación es un proceso muy frecuente en programación. Esta operación es también un proceso que las personas encuentran comúnmente en sus rutinas diarias. Por ejemplo, cada elemento de la colección de datos de una agenda telefónica tiene un campo nombre, dirección y un número de teléfono. Una colección de datos clasificados se puede almacenar en un archivo, un vector o tabla, una lista enlazada o un árbol. Cuando los datos están almacenados en vectores, tablas (arrays), lista enlazadas o arboles, la ordenación se denomina ordenación interna. Cuando los datos a clasificar se encuentran almacenados en archivos, en soporte de almacenamiento masivo (cintas o discos) el proceso de ordenación se denomina ordenación externa.

Es un proceso utilizado en sistema de actualización, y en casos en que es necesario varias listas ordenadas. También es la única forma que hay para el ordenamiento de archivos, debido a la imposibilidad de almacenarlos en memoria y a limitaciones en el tiempo, por la cantidad de elementos a ordenar.

Es el caso más simple, cuando se intercalan dos listas o archivos. Suponga que se tienen los arreglos ordenados A1 y A2 con elementos n1 y n2 respectivamente. Se desean intercalar en el arreglo A3.

El problema de ordenamiento se puede reducir a uno de intercalación. Si se quiere ordenar una lista muy grande, se puede pensar en subdividir esa lista en sublistas de un elemento, luego intercalar dos sublistas, para obtener sublistas ordenadas de dos elementos, luego de cuatro, etc., hasta obtener la lista ordenada, o tomar sublistas de L elementos, ordenarlas por cualquier algoritmo de ordenamiento y luego intercalarlas.

Existe diferentes tipos de métodos de intercalación, entre ellos se destacarán los siguientes:

Intercalación Simple: 

Se tienen dos archivos ordenados y se obtiene al final un solo archivo ordenado que contiene los elementos de los dos archivos iniciales.

Para utilizar el método se inicia con un vector de n posiciones. Comencemos con el subíndice i en la segunda posición incrementa en 1, el elemento del subíndice del vctor se elimina de la secuencia y se reinserta en el vector en la posición adecuada.