Ordenamiento

Páginas: 5 (1011 palabras) Publicado: 4 de enero de 2013
Informe Tarea
Ordenamiento de Grandes Archivos de Texto

Introducción
Si se requiere el ordenamiento de un archivo, dependiendo del tamaño de este, la ejecución puede llegar a requerir mucho más que los recursos disponibles en memoria principal del computador. Así que, se hace necesario diseñar un mecanismo para ejecutar tareas en segundo plano (esto es, ordenar bloques del archivo original,tanto como sea posible en memoria principal), y luego ir construyendo la solución (correspondiente al archivo completamente ordenado). Esta Tarea tiene como objetivo la ordenación de una lista de números enteros en un archivo de 2 GB utilizando la técnica de Multiway Mergesort, para esto se seguirán los siguientes pasos: 1. Particionar el archivo a ordenar en bloques manejables en memoriaprincipal. 2. Ordenar cada uno de ellos utilizando algún algoritmo eficiente (por ejemplo, quicksort). 3. Construir el archivo de salida uniendo los distintos bloques ya ordenados usando un algoritmo eficiente (por ejemplo, la operación merge de mergesort).

Análisis del problema
El problema consiste en dividir el archivo ya sea contando las líneas si no se conoce a priori el número de líneas. Y si seconoce entonces se introducirá en la terminal. Para el caso del archivo de prueba oficial es necesario dividirlo en 21 partes para que cada una sea de aproximadamente 100MB. Posteriormente se ordenarán los archivos y finalmente se ordenará todas usando Mergesort. Al particionar los archivos se dividirá el número de líneas en el numero de partes y se distribuirá una línea más por cada archivohasta completar el resto si la división es inexacta

Solución del problema
Algoritmo de solución
El algoritmo se solución utiliza en el cuerpo del programa 3 funciones
String[] particionar(String nombreArchivo, int NPartes),

que divide el

archivo original en Npartes
void ordenarArchivo(String nombreArchivo)

ordena el archivo usando quicksort y

buscando la mediana de entre loselementos Se usa la función ordenarArchivo para ordenar cada archivo por separado. Esta es una función de tipo void que guarda en el mismo archivo de entrada los elementos ordenados. Finalmente la función void generarArchivoSalida(String[] archOrdenados, String archSalida)recibe como entrada el vector de nombres de archivos en que el original fue separado, estos archivos ya están ordenados. La funcióngenera un archivo de salida con los elementos de todos los archivos ordenados utilizando Multiway Mergesort y escribiendo en el archivo final, lo que requiere la utización de un Heap .

Diseño
Para implementar la funcion ordenarArchivo(String nombreArchivo) se utiliza el algoritmo de quicksort, esto consiste en escoger un pivote, que en este caso particular se elige tomando el primer, el ultimoy el elemento de en medio y seleccionando la mediana entre ellos. Este es un algoritmo recursivo que se aplica a ambas partes, menores y mayores del pivote escogido hasta que el arreglo queda completamente ordenado. La función void generarArchivoSalida(String[] archOrdenados, String archSalida) utiliza la técnica de multiway Mergesort, esto se aprovecha de que cada archivo ya está ordenado , paraordenar el conjunto usando un Heap. También se utiliza la clase Pair que gurda el elemento y de qué archivo proveniene. Así cuando se extrae el mínimo de todas las listas de sabe de qué lista se debe agregar un nuevo elemento al Heap, se continúa así hasta que se acaban todos los elementos de los archivos.

Implementación
El cuerpo del programa que interactúa con el usuario y aplica las 3funciones ya mencionadas

La función static public String[] particionar(String nombreArchivo,int Npartes,int TotLin) particiona el archivo en tantas partes como se requiera en la entrada y devuelve el vector de strings con los nombres de los archivos.

La funcion static public void quicksort(int [] x,int ip, int iu)aplica recursivamente quicksort a ambos lados del pivote
static public int...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Ordenador
  • El Ordenador
  • ordenadores
  • El ordenador
  • El ORDENADOR
  • Ordenes
  • Ordenador
  • Ordenadores

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS