Ordenamiento externo

Ordenamiento externo

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.

  1. Leanse 100MB de información en la memoria principal y ordenense utilizando un algoritmo tradicional (típicamente quicksort).
  2. Escríbase la información ordenada en el disco.
  3. 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.
  4. 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.
  5. 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.

Otro ejemplo es el algoritmo de ordenamiento por mezcla equilibrada, que es una optimización del anterior.

Referencias

  • 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


Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • 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 …   Enciclopedia Universal

  • Ordenamiento — puede referise a: En derecho: Ordenamiento jurídico, el conjunto de normas globales que rigen en una determinada época y en un lugar determinado. Ordenamiento jurídico de la Orden de Malta, el Ordenamiento jurídico especial de la Orden de Malta.… …   Wikipedia Español

  • Ordenamiento por mezcla equilibrada — El algoritmo de Ordenamiento por mezcla equilibrada (o mezcla natural) es un algoritmo de ordenación externa estable basado en la técnica divide y vencerás y es una optimización del método de mezcla directa. Descripción La idea básica es realizar …   Wikipedia Español

  • Ordenamiento por mezcla — El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. Es de complejidad O(n log n). Contenido 1 Descripción 2 Implementaciones 2.1 Perl …   Wikipedia Español

  • Algoritmo de ordenamiento — Quicksort en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote. En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por …   Wikipedia Español

  • Join — La sentencia join en SQL permite combinar registros de dos o más tablas en una base de datos relacional. En el Lenguaje de Consultas Estructurado (SQL), hay tres tipo de JOIN: interno, externo, y cruzado. En casos especiales una tabla puede… …   Wikipedia Español

  • Magnetoquímica — Los orbitales d de los metales de transición participan en la mayoría de los estudios magnetoquímicos …   Wikipedia Español

  • Wikipedia:Café (todos) — Atajos WP:CWP:C …   Wikipedia Español

  • Angustia — Saltar a navegación, búsqueda Etimologia: del indoeuropeo *anghu , moderación. relacionado con la palabra alemana Angst. La angustia es un estado afectivo de carácter penoso que se caracteriza por aparecer como reacción ante un peligro… …   Wikipedia Español

  • Derecho administrativo (España) — Saltar a navegación, búsqueda Contenido 1 Concepto derecho administrativo Español 2 Evolución del derecho administrativo Español 3 Potestades administrativas …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”