Ordenacion archivos

  • View
    167

  • Download
    2

Embed Size (px)

Text of Ordenacion archivos

1. MTODOS DE ORDENACIN MELINA CASTAEDA PREZ. DANIEL MARTNEZ SUASTEGUI. SILVERIO QUIONEZ GARCA. GUSTAVO AXEL SAUCEDO ROMN. 2. QU ES ORDENACIN? LA ORDENACIN O CLASIFICACIN DE DATOS (SORT EN INGLS) ES UNA OPERACIN CONSISTENTE EN DISPONER UN CONJUNTO ESTRUCTURA DE DATOS EN ALGN DETERMINADO ORDEN CON RESPECTO A UNO DE LOS CAMPOS DE ELEMENTOS DEL CONJUNTO. POR EJEMPLO, CADA ELEMENTO DEL CONJUNTO DE DATOS DE UNA GUA TELEFNICA TIENE UN CAMPO NOMBRE, UN CAMPO DIRECCIN Y UN CAMPO NMERO DE TELFONO; LA GUA TELEFNICA EST DISPUESTA EN ORDEN ALFABTICO DE NOMBRES. LOS ELEMENTOS NUMRICOS SE PUEDEN ORDENAR EN ORDEN CRECIENTE O 3. EJEMPLO DE ORDENACIN Por ejemplo, para una gua telefnica, la lista est clasificada en orden ascendente por el campo clave k, donde k[i] es el nombre del abona- do (apellidos, nombre). , 4. ORDENACIN POR BURBUJA Este mtodo es clsico y muy sencillo, aunque por desgracia poco eficiente. La ordenacin por burbuja (< aux Hacer: Desplazar elemento una posicin. Comprobar valor del siguiente elemento. Definir nuevaPos como posicin original del ltimo elemento desplazado. Fin mientras. 11. ALGORITMO DE SHELL. Se suele denominar tambin ordenacin por disminucin de incremento (gap). La idea general del mtodo (algoritmo) es la siguiente: 504 88 513 62 908 171 898 277 654 427 150 510 612 675 750 704 12. ALGORITMO DE SHELL. l. Se divide la lista original (16 elementos, en este ejemplo) en ocho grupos de dos (considerando un incremento o intervalo de 16/2 = 8). 13. 2. Se clasifica cada grupo por separado (se comparan las parejas de elementos y si no estn ordenados se intercambian entre s de posiciones). 14. 3. Se divide ahora la lista en cuatro grupos de cuatro (intervalo o salto de 8/2 = 4) y nuevamente se clasifica cada grupo por separado. 4. Un tercer paso clasifica dos grupos de ocho registros y luego un cuarto paso completa el trabajo clasificando los 16 registros. 15. 2. Se clasifica cada grupo por separado (se comparan las parejas de elementos y si no estn ordenados se intercambian entre s de posiciones). 16. ORDENACIN RPIDA. La idea bsica de la ordenacin rpida de un array (lista) es: Elegir un elemento del array denominado pivote. Dividir o partir el array original en dos subarrays o mitades (sublistas), de modo que en una de ellas estn todos los elementos menores que el pivote y en la otra sublista todos los elementos mayores que el pivote. Las sublistas deben ser ordenadas, independientemente, del mismo modo, lo que conduce a un algoritmo recursivo. 17. ALGORITMO DE ORDENACIN RPIDA. 1. Inicializar 1 a Primero (primer ndice del array) 2. Inicializar J a Ultimo (ltimo ndice del array) 3. Seleccionar el elemento pivote (trmino Central) Central ~ A [(Primero + Ultimo) div 2] 4. Repetir 4.1. Mientras A[I] < Central hacer 1 = 1 +1 Fin Mientras 4.2. Mientras A [J] > Central hacer J = J - 1 Fin Mientras 18. ALGORITMO DE ORDENACIN RPIDA. 4.3. Si 1 J 5. Si J > Primero, llamar al procedimiento Partir, para dividir la sublista izquierda [Primero J] 6. Si 1 < Ultimo, llamar al procedimiento Partir, para dividir la sublista derecha [1 Ultimo] 19. ORDENACIN POR MEZCLA. El proceso consiste en dividir la lista en dos mitades y cada una de las mitades en otras mitades. Este proceso se repite hasta que cada sublista contiene, cada una, una entrada 20. ALGORITMO DE ORDENACIN POR MEZCLA. l. Dividir la lista en dos mitades. 2. Ordenar la sublista izquierda. 3. Ordenar la sublista derecha. 4. Mezclar las dos sublistas juntas. 1. Si Primero < Ultimo, entonces {ndices de la lista original} 1.1. Central f- (Primero +Ultimo) div 2 {punto de divisin para la particin} 1.2. Llamar a OrdMezcla a [ Primero .. Central ) 1.3. Llamar a OrdMezcla a [Central+1 .. Ultimo] 1.4. Mezclar a [Primero .. Central] con a [Cen tral+l. .Ultimo] 21. Este algoritmo de ordenacin est basado en la estructura de montculo. Montculo Se define un montculo de tamao n como un rbol binario completo de n nodos, tal que el contenido de cada nodo es mayor o igual al contenido de su padre. Mtodo de Ordenacin por Montculos 22. El nodo ocupara la posicin 1 en el arreglo, y en la posicin 2 y 3 estarn sus nodos hijo izquierdo y derecho, respectivamente. La representacin del rbol del ejemplo en un arreglo es: Mtodo de Ordenacin por Montculos Es claro que a partir de esta definicin de montculo la raz del rbol (o primer elemento del arreglo) es el elemento ms pequeo; en definitiva, V[l] siempre tendr el elemento mas pequeo. Segn esto podemos descomponer el mtodo de ordenacin heapsort en los siguientes pasos: 1. Construir un montculo inicial con todos los elementos del vector: V[lJ, V[2J, ... V[nJ 2. Intercambiar los valores de . V[lJ y V[nJ (siempre se queda el mximo en el extremo). 3. Reconstruir el montculo con los elementos V[lJ, V[2J, ... V[n - 1]. 4. Intercambiar los valores de V[lJ y V[n - 1J. 5. Reconstruir el montculo con los elementos V[l], V[2J, '" V[n - 2]. 23. Segn el algoritmo debemos considerar dos problemas: construir el montculo inicial y cmo restablecer los montculos intermedios. Como ahora veremos, la solucin a ambos problemas va a ser mediante una misma rutina. Consideremos que ya est construido el montculo inicial y se ha realizado el intercambio. La figura nos muestra esta , situacin Mtodo de Ordenacin por Montculos 24. Mtodo de Ordenacin por Montculos 25. Para restablecer el montculo hay dos posibilidades: V[l] es menor o igual que los valores de sus hijos, entonces la propiedad del montculo no se ha roto. En otro caso, el elemento mnimo que necesitamos poner en V[ 1] es o su hijo izquierdo o su hijo derecho (V[2], V[3], respectivamente). Por lo que se determina el menor de sus hijos y ste se intercambia con V[l). El proceso contina repitiendo las mismas comparaciones entre el nodo intercambiado y sus nodos hijos; as hasta llegar a un nodo en el que no se viole la propiedad de montculo, o estemos en un nodo hoja. La figura nos muestra el proceso de restablecer la condicin de montculo en el rbol resultante del intercambio; este proceso se expresa diciendo que el nodo situado en la cspide del rbol se deja hundir por el camino de claves mnimas Mtodo de Ordenacin por Montculos 26. Mtodo de Ordenacin Binsort Este mtodo, tambin llamado clasificacin por urnas, plantea conseguir tiempos de ejecucin menores de O(n lag n) para ordenar n elementos siempre que se conozca algo acerca del tipo de las claves por las que se estn ordenando. Este mtodo utiliza urnas, cada urna contiene todos los registros con una misma clave. El proceso consiste en examinar cada registro R a clasificar y situarle en la urna 1, coincidiendo i con el valor del campo clave de R. En la mayora de los casos en que se utilice el algoritmo ser necesario guardar ms de un registro en una misma urna por tener claves repetidas. Entonces estas urnas hay que concatenarlas en el orden de menor ndice de urna a mayor, as quedar el arreglo en orden creciente respecto al campo clave. En la figura se tiene un arreglo de 1 a m urnas. 27. Mtodo de Ordenacin Binsort 28. Mtodo de Ordenacin Binsort Este mtodo se puede considerar como una generalizacin de la clasificacin por urnas Aprovecha la estrategia de la forma ms antigua de clasificacin manual, consistente en hacer diversos montones de fichas, cada uno caracterizado por tener sus componentes un mismo dgito (letra si es alfabtica) en la misma posicin; estos montones se recogen en orden ascendente y se reparte de nuevo en montones segn el siguiente dgito de la clave. Para centrarnos en lo que estamos diciendo, supngase que tenemos que ordenar estas fichas identificadas por tres dgitos: 345, 721,425,572,836,467,672,194,365,236,891, 746,431,834,247,529,216,389 29. Mtodo de Ordenacin Binsort Tomando los montones en orden, la secuencia de fichas queda: 721 891 431 572 672 194 834 345 425 365 836 236 746 216 467 247 529 389 De esta secuencia podemos decir que est ordenada respecto al dgito de menor peso. Pues bien, ahora de nuevo distribuimos la secuencia de fichas en montones respecto al segundo dgito: Tomando de nuevo los montones en orden, la secuencia de fichas queda as: 216 721 425 529 431 834 836 236 345 746 247 365 467 572 672 389 891 194