Ordenamiento externo 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 un disco duro) tiene que utilizarse en el proceso.
Un ejemplo de ordenamiento externo es el algoritmo de ordenamiento por mezcla. Supongamos que 900 MB de información deben ser ordenados utilizando únicamente 100 MB de RAM.
Léanse 100MB de información en la memoria principal y ordenense utilizando un algoritmo tradicional (típicamente quicksort).
Escríbase la información ordenada en el disco.
Repítanse los pasos 1 y 2 hasta que toda la información esté ordenada en pedazos de 100 MB. Ahora se deben mezclar todos los pedazos ordenados.
Léanse los primeros 10MB de cada pedazo ordenado a la memoria principal (total de 90 MB) y destínense los 10 MB restantes para el buffer de salida.
Ordénense los nueve pedazos mezclándolos y grábese el resultado en el buffer de salida. Si el buffer de salida está lleno, escríbase al archivo destino final. Si cualquiera de los 9 buffers leídos queda vacío, se llena con los siguientes 10 MB de su pedazo original de 100 MB o se marca este como completado si ya no hay registros remanentes.
Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.4: External Sorting, pp.248–379.
Enlaces externos
Notas de Ordenamiento Externo(enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última)..
Datos:Q209687
Octubre 15, 2022
ordenamiento, externo, término, genérico, para, algoritmos, ordenamiento, pueden, manejar, grandes, cantidades, información, ordenamiento, externo, requiere, cuando, información, tiene, ordenar, cabe, memoria, principal, computadora, típicamente, tipo, memoria. Ordenamiento externo es un termino generico para los algoritmos de ordenamiento que pueden manejar grandes cantidades de informacion El ordenamiento externo se requiere cuando la informacion que se tiene que ordenar no cabe en la memoria principal de una computadora tipicamente la RAM y un tipo de memoria mas lenta tipicamente un disco duro tiene que utilizarse en el proceso Un ejemplo de ordenamiento externo es el algoritmo de ordenamiento por mezcla Supongamos que 900 MB de informacion deben ser ordenados utilizando unicamente 100 MB de RAM Leanse 100MB de informacion en la memoria principal y ordenense utilizando un algoritmo tradicional tipicamente quicksort Escribase la informacion ordenada en el disco Repitanse los pasos 1 y 2 hasta que toda la informacion este ordenada en pedazos de 100 MB Ahora se deben mezclar todos los pedazos ordenados Leanse los primeros 10MB de cada pedazo ordenado a la memoria principal total de 90 MB y destinense los 10 MB restantes para el buffer de salida Ordenense los nueve pedazos mezclandolos y grabese el resultado en el buffer de salida Si el buffer de salida esta lleno escribase al archivo destino final Si cualquiera de los 9 buffers leidos queda vacio se llena con los siguientes 10 MB de su pedazo original de 100 MB o se marca este como completado si ya no hay registros remanentes Otro ejemplo es el algoritmo de ordenamiento por mezcla equilibrada que es una optimizacion del anterior Referencias EditarDonald Knuth The Art of Computer Programming Volume 3 Sorting and Searching Third Edition Addison Wesley 1997 ISBN 0 201 89685 0 Section 5 4 External Sorting pp 248 379 Enlaces externos EditarNotas de Ordenamiento Externo enlace roto disponible en Internet Archive vease el historial la primera version y la ultima Datos Q209687 Obtenido de https es wikipedia org w index php title Ordenamiento externo amp oldid 120648857, wikipedia, wiki, leyendo, leer, libro, biblioteca,
