Ordenacion externa en java

ESTRUCTURA DE DATOS

1
ORDENACION EXTERNA

ESTRUCTURA DE DATOS

S.E.P

S.N.E.S.T

D.G.E.S.T

INSTITUTO TECNOLÓGICO
del Istmo
ING. SISTEMAS COMPUTACIONALES

MATERIA: ESTRUCTURA DE DATOS TEMA: ORDENACIÓN EXTERNA PRESENTA: TRUJILLO VICTORIANO NANCI CATEDRATICO: JIMENEZ AQUINO MARIA CECILIA GRUPO: TERCERO “Y” NÙMERO DE CONTROL: 09190018

JUCHITAN DE ZARAGOZA, OAXACA; 3 DEDICIEMBRE DE 2010

2
ORDENACION EXTERNA

ESTRUCTURA 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. Nos centraremos en los métodos más populares, analizando la cantidad de comparaciones que suceden, el tiempo que demora y revisando el código,escrito en Java, de cada algoritmo. Este informe nos permitirá conocer más a fondo cada método distinto de ordenamiento, desde uno simple hasta el más complejo. Se realizaran comparaciones en tiempo de ejecución, prerrequisitos de cada algoritmo, funcionalidad, alcance, etc. En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en unasecuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —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 ordenadaspara 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 como cintas, discos,etc. El proceso de ordenar los datos almacenados en varios archivos se conoce con el nombre de fusión o mezcla, entendiendo por este concepto la combinación o intercalación de dos o más secuencias ordenadas en una única secuencia ordenada. Debe hacerse hincapié en que sólo se colocan en la memoria principal de la computadora los datos que se pueden acceder directamente.

3
ORDENACION EXTERNAESTRUCTURA DE DATOS

[[*ORDENACIÓN EXTERNA*]]
----Algoritmos Ordenación Externa---Es un término genérico para los algoritmos de ordenamiento que pueden manejar grandes cantidades de información. El ordenamiento externo se requiere cuando la información que se tiene que ordenar no cabe en la memoria principal de una computadora (típicamente la RAM) y un tipo de memoria más lenta (típicamente undisco duro) tiene que utilizarse en el proceso. 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 externo (Archivos) y su ordenación es más lenta que la interna.

**ALGORITMOS DE ORDENACIÓN** **EXTERNA**
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:  Dividir el archivo en n subarchivos de tamaño 1 e intercalar pares adyacentes (inconexos) de archivos. Entoncestenemos más o menos n/2 archivos de tamaño 2.  Repetir el proceso hasta que solo reste un archivo de tamaño n.

*** ~ESTABILIDAD DEL ALGORITMO~***
4
ORDENACION EXTERNA

ESTRUCTURA DE DATOS

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 problema. Sin embargo, asumamos...