Modelos óptimos de intercalación
José Padrón C.I 28.462.837 P. no númerica 2 SAIA 2020-1 IUPSM Barcelona
Introducción
Ordenar es simplemente colocar información de una manera especial basándonos en un criterio de ordenamiento. El propósito principal de un ordenamiento es el de facilitar las búsquedas de los registros del conjunto ordenado. Un ordenamiento es conviene usarlo cuándo se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.
Es importante destacar que existen diferentes técnicas de ordenamiento como lo es; El Método Burbuja, que consiste en comparar pares de valores de llaves; Método Selección, el cual consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo; y por ultimo el Método Intercalación, con el cual se combinan los sub-archivos ordenados en una sola ejecución.
¿Qué es ordenamiento?
Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento. El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia, tal que represente un orden, el cual puede ser numérico, alfabético o alfanumérico, ascendente o descendente.
El propósito principal de un ordenamiento es el de facilitar las búsquedas de los registros del conjunto ordenado. El método de ordenamiento es conviene usar Cuándo se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.
Métodos de Ordenamiento
Existen diferentes métodos de ordenamiento de datos como lo son:
1) El Método Burbuja: también conocido como El bubble sort, este método de ordenamiento consiste en comparar pares de valores de llaves, e intercambiarlos si no se encuentran en sus posiciones correctas.
2) Método Selección: consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo.
3) Método Intercalación: es en la cual se combinan los sub-archivos ordenados en una sola ejecución. Es un proceso bastante utilizado en sistemas de actualización. También es la única forma que hay para el ordenamiento de archivos, debido a la imposibilidad física de almacenarlos en memoria y a limitaciones en el tiempo, por la cantidad de elementos a ordenar. Existen diferentes tipos de intercalación, de los cuales se puede destacan:
Intercalación Binaria: El algoritmo de ordenación por intercalación simple requiere una exploración o búsqueda secuencial para localizar la posición de un elemento en la sublista ordenada, si en lugar de considerar una búsqueda secuencial se realizara una búsqueda binaria se mejoraría considerablemente el algoritmo y se aumentaría la velocidad de ejecución. Esta modificación se conoce como método de intercalación binaria. Este algoritmo utiliza la técnica de dividir y conquistar por lo tanto, divide al vector y toma un elemento pivote y compara contra él los elementos del vector dividido.
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.se comienza con el subíndice i, en la segunda posición incrementando en 1, el elemento del subíndice del vector se elimina de la secuencia y se reinserta en el vector en la posición adecuada.
Intercalación Balanceada: Una intercalación balanceada de m vías utiliza m archivos de entrada y m archivos de de salida. Las k listas ordenadas se distribuyen en forma uniforme en los m archivos de entrada. Se intercalan las listas de cada uno de los archivos, distribuyendo en forma uniforme las listas resultantes en los archivos de salida (de mayor tamaño que las iniciales). Se repite el último paso hasta que un archivo de salida contiene una lista ordenada.
Intercalación Polifásica: Una intercalación polifásica de m vías utiliza 2*m-1 archivos de entrada y 1 archivo de salida. Las k listas se distribuyen en forma no uniforme en los 2*m-1 archivos de entrada.
Se intercalan las listas (de mayor tamaño) en el archivo de salida. El archivo de entrada que primero queda vacío pasa a ser archivo de salida y el archivo de salida pasa a ser de entrada. Se repiten los 2 últimos pasos hasta que un archivo de salida contenga la lista ordenada.
Tipos de ordenamientos:
Los 2 tipos de ordenamientos óptimos según la estructura de datos a utilizar son: los internos y los externos.
Los internos: Son aquellos en que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento sea el mismo, este ordenamiento se aplican cuando el conjunto de datos a clasificar es lo suficientemente pequeño.
Externos: Es cuando los datos a clasificar se encuentran almacenados en archivos, en soportes de almacenamiento masivo (cintas o discos) el tiempo de acceso a lectura y escritura influye en la eficiencia del ordenamiento, por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada.
Búsqueda Binaria
El método de búsqueda binaria divide el total de los elementos en dos, comparando el elemento buscado con el central, en caso de no ser iguales, se determina si el elemento buscado es menor o mayor al central, para determinar si la búsqueda continua del lado izquierdo (menor) o derecho (mayor) del central, repitiendo el mismo proceso de división y comparación, hasta encontrar el elemento buscado o que la división ya no sea posible.
Debemos destacar que este método de búsqueda solo funciona con estructuras de datos previamente ordenadas, dividiendo cada vez a la mitad el proceso de búsqueda, lo que hace que el método sea más eficiente.
Ejemplo: si tenemos una estructura ordenada 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 y estamos buscando el número 5, el resultado de la búsqueda nos mostraría la posición 4 y el proceso terminaría ya que el elemento buscado no es diferente al que está en la posición central.
Este proceso debe sumar la posición inicial y la final, dividiendo el resultado de la suma entre dos para obtener la posición central generada por el cociente de la división, en este caso es (0+9)/2=4, esta posición se compara con el elemento que estamos buscando y como son iguales la búsqueda se detiene mostrando la posición donde lo encontró.
