Ordenacion externa en java
Ordenacion externa en java gy Kish18 Ac•Ka6pR 04, 2010 7 pagos ESTRUCTURA DE DATOS ORDENACION EXTERNA S. E. p S. N. E. S. T D. G. E. S. T INSTITUTO TECNOLÓGICO del Istmo or7 to View nut*ge ING. SISTEMAS COM MATERIA: ESTRUCTU PRESENTA: TRUJILLO ENACION EXTERNA EDRATICO: JIMÉNEZ AQUINO MARIA CECILIA GRUPO: TERCERO ‘Y» NUMERO DE CONTROL: 09190018 JUCHITAN DE ZARAGOZA, OAXACA; 3 DE DICIEMBRE DE 2010 2 ESTRUCWRA DE DATOS INTRODUCCIÓN Los algoritmos de ordenamiento nos permiten, como su nombre lo dice, ordenar. En este caso, nos servirán para ordenar vectores o matrices con valores asignados aleatoriamente. ???o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos En la actualidad es muy común procesar tales volúmenes de información que los datos no pueden almacenar en las memorias principales de la computadora.
Estos datos, organizados en archivos, se guardan en dispositivos de almacenamiento secundario tales
Existen otros tipos de memoria externa que son los USB de almacenamiento entre otros. La Ordenación externa de los datos están en un dispositivo de almacenamiento xterno (Archivos)y su ordenación es más lenta que la interna. Intercalación (MERGE) es el proceso de combinar dos o más archivos (arreglos) ordenados en un tercer archivo ordenado. Este algoritmo de comparación, es estable ya que se mantiene el orden relativo de registros con claves iguales. Es un tipo de algoritmo «DIVIDE Y VENCERAS». Fue inventado por John Von Newmann en 1945.
Esta técnica funciona de la siguiente manera: Cl Dividir el archivo en n subarchivos de tamaño 1 e intercalar pares adyacentes (inconexos) de archivos. Entonces tenemos más o menos n/2 archivos de tamaño 2. Cl Repetir el proceso hasta que solo reste un archivo de tamaño n. -ESTABILIDAD DEL 4 Cuando los elementos iguales son indistinguibles, como con los enteros, o más generalmente, cualquier dato en el que el elemento es la llave, la estabilidad no es un pro cualquier dato en el que el elemento es la llave, la estabilidad no es un problema.
Sin embargo, asumamos que los siguientes pares de números se van a ordenar por su primera componente: (4, 1) (3, 7) (3, 1) (5, 5) En este caso, el resultado puede ser dos ordenaciones posibles, uno que mantiene el orden relativo e los registros con llaves iguales y otro que no: (3, 7) (3, 1) (4, l) (5, 6) (se mantiene) (3, 1) (3, 1) (5, 6) (se cambia) os ordenamientos inestables pueden cambiar el orden relativo, pero en el ordenamiento estable nunca sucede esto.
DEL MERGESORT es mas eficiente que quicksort para algunos tipos de listas con datos a ordenar que pueden ser solamente accesadas eficientemente de manera secuencial, y esto es popular en lenguajes de programación como LISP, donde el acceso a estructuras de datos de forma secuencial es muy común. DE Al ordenar n elementos, este ordenamiento tiene un tiempo romedio y de un peor caso de log n).
Si el tiempo de ejecución de la intercalación para una lista de tamaño n es T(n), entonces T(n) = 2T(n/2) + n siguiendo la definición del algoritmo (aplicar el algoritmo a dos listar de la mitad de tamaño de la lista original, y añadir los n pasos necesarios para mezclar el resultado en dos listas). En el peor caso hace: (n rlg nl – 2rlg nl 1) comparaciones, lo qu el resultado en dos listas). En el peor caso hace: (n rlg n] – 2rlg m + 1) comparaciones, lo que es entre (n Ign n + 1) y (n Ig n + n + O(lg n)).
Para una cantidad muy grande de elementos y una ista de entrada ordenada aleatoriamente, el número esperado (promedio) de comparaciones se aproxima menos que el peor caso donde a es: «*-INTERCALACIÓN EN DISPOSITIVOS DE MEMORIA La intercalación directa es un método de ordenación inherentemente secuencial y debido a esto es muy práctico para usarse en dispositivos de almacenamiento en cinta como también en dispositivos de entrada y salida. Requiere muy poca memoria y la memoria requerida no cambia con el numero de elementos de datos. Ejemplo.
Si tuviéramos cuatro dispositivos de cinta, trabajaría así: 1 . Divide los datos que se van a almacenar la mitad y coloca la mitad en cada una de las clntas. 2. Mezcla los pares individuales de registros de las dos cintas; escribe partes de dos registros alternadamente a cada una de las dos cintas de salida. 3. Mezcla los pedazos de registros de las dos cintas de salidas en pedazos de cuatro registros; escribe estos alternadamente a las dos cintas de entrada originales. 4. Mezcla los pedazos de cuatro registros en pedazos de ocho registros; escribe estos alternadamente a las dos cintas de salida originales. . Repetir el de ocho registros; escribe estos alternadamente a las dos cintas de salida originales. 5. Repetir el proceso hasta que se tiene un pedazo que contiene todo los datos, ordenados. Por esta misma razón es muy útil para ordenar datos en disco cuando esta es muy grande para ser procesada en memoria primaria. En los dispositivos de cinta que pueden funcionar en ambos sentidos, se pueden hacer mezclas en las pasadas en ambas direcciones, eliminando el tiempo de rebobinado. Este es probablemente el más utilizado por su fácil comprensión.
La idea central de este algoritmo consiste en la realización sucesiva de una partición y una fusión que produce secuencias ordenadas de longitud cada vez mayor. En la primera pasada, la partición es de longitud 1 y la fuslón o mezcla produce secuencias ordenadas de longitud 2. En la segunda pasada, la partición es de longitud 2 y la fusión o mezcla produce secuencias ordenadas de longitud 4. Este proceso se repite hasta que la longitud de la secuencia para la partición sea: Parte entera ((n +1)/2).
Donde n representa el número de elementos del archivo original. 6 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 Fl y F2. F: og 75 1468 29 17 31 25 0405 13 18 72 46 61 PRIMERA PASADA se les denominara Fl y F2 F: 09 75 1468 29 17 31 25 0405 13 18 72 46 61 PRIMERA PASADA Partición en secuencias de longitud 1 . Fl : 09′ 14 29′ 31 04 13 72′ 61′ F2: 75′ 68 17′ 25′ 05′ 18′ 46′ Fusión en secuencias de longitud 2. : 09 75′ 14 68′ 17 29′ 25 31′ 04 05′ 13 18′ 46 72′ 61′ SEGUNDA PASADA Partición en secuencias de longitud 2. Pl: 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 partición en secuencias de longitud 4. Pl: 09 14 68 75′ 04 05 13 18′ F2: 17 25 9 31 45 61 72′ Fuslón en secuencias de longltud 8. F: og 14 17 25 29 31 68 75′ 04 OS 13 1846 61 72′ CUARTA PASADA partición en secuencias de longitud 8. 09 14 17 25 29 31 68 75′ F2: 0405 13 18 46 51 72′ Fusión en secuencias de longitud 16. p: 04 05 09 13 14 17 18 25 29 31 46 61 68 72 75 A continuación se presenta el algoritmo de ordenación de archivos por el método de mezcla directa. DIRECTA (F, FL F2, El algoritmo ordena los elementos del archivo F por el método de mezcla directa. Utiliza archivos auxiliares Fl y F2. N es el número de elementos del archivo F PART es una variable de tipo entero. 1. Hacer PART
