Algoritmos de ordenamiento externos

Ordenamiento por intercalación directa
Ordenamiento por intercalación natural
Ordenamiento por intercalación balanceada
Ordenamiento por intercalación polifásica

1. Universidad De Cuenca Nombres: David Valladares Edisson Sigua Paúl Arévalo Temas: Ordenamientos Externos

2. Indice Proyectos en GitHub Ordenamiento por intercalación DIRECTA Ordenamiento por intercalación NATURAL Ordenamiento por intercalación BALANCEADA Ordenamiento por intercalación POLIFÁSICA

3. Proyectos en GitHub Intercalación Directa y Natural https://github.com/jeims17/IntercalacionDirectaNatural Intercalación Balanceada https://github.com/jeims17/IntercalacionBalanceada Intercalación Polifásica https://github.com/jeims17/IntercalacionPolifasica

4. ORDENAMIENTO POR INTERCALACIÓN DIRECTA

5. Ordenamiento por Intercalación Directa Probablemente es el método de ordenación externa más utilizado por su fácil comprensión. Su idea central está basada en la estrategia de hacer subdivisiones y fusiones sucesivas de secuencias de tamaño cada vez más grande. Este proceso se repite hasta que el número de pasadas sea la parte entera de ((n + 1)/2) siendo n el número de registros existentes en el archivo.

6. Ejemplo F: F1: F2: 09 75 05 68 01 25 14

7. Ejemplo F: F1: F2: 75 05 68 01 25 14 09´

8. Ejemplo F: F1: F2: 05 68 01 25 14 09´ 75´

9. Ejemplo F: F1: F2: 05 01 25 14 09´ 68´ 75´

10. Ejemplo F: F1: F2: 05 01 25 09´ 68´ 75´ 14´

11. Ejemplo F: F1: F2: 05 01 09´ 68´ 25´ 75´ 14´

12. Ejemplo F: F1: F2: 01 09´ 68´ 25´ 75´ 14´ 5´

13. Ejemplo F: F1: F2: 09´ 68´ 25´ 01´ 75´ 14´ 05´

14. Ejemplo F: F1: F2: 09 75´ 68´ 25´ 01´ 14´ 5´

15. Ejemplo F: F1: F2: 09 75´ 14 68´ 25´ 01´ 05´

16. Ejemplo F: F1: F2: 09 75´ 25´ 14 05 68´ 01´

17. Ejemplo F: F1: F2: 09 75´ 25´ 14 01´ 05 68´

18. Ejemplo F: F1: F2: 25´ 14 01´ 05 68´ 09 75´

19. Ejemplo F: F1: F2: 25´ 01´ 05 09 75´ 14 68´

20. Ejemplo F: F1: F2: 01´ 09 75´ 05 25´ 14 68´

21. Ejemplo F: F1: F2: 09 75´ 05 25´ 14 68´ 01´

22. Ejemplo F: F1: F2: 09 14 68 75´ 05 25´ 01´

23. Ejemplo F: F1: F2: 09 14 05 68 25´ 01 75´

24. Ejemplo F: F1: F2: 05 25´ 01 09 14 68 75´

25. Ejemplo F: F1: F2: 09 14 68 75´ 01 05 25´

26. Ejemplo F: F1: F2: 01 05 68 09 75´ 25 14

27. Archivos utilizados

28. Código

29. ORDENAMIENTO POR INTERCALACIÓN NATURAL

30. Ordenamiento por Intercalación Natural Este ordenamiento es una optimización del algoritmo de intercalación directa. La idea central de este ordenamiento consiste en realizar las particiones tomando secuencias ordenadas de tamaño máximo en lugar de secuencias fijas. Luego se fusiona estas particiones en el archivo original. Este ordenamiento se realiza hasta que uno de los archivos de las particiones queda vacío.

31. Ejemplo F: F1: F2: 09 15 30 64 01 15 20

32. Ejemplo F: F1: F2: 30 01 15 20 09 15 64

33. Ejemplo F: F1: F2: 30 01 15 09 15 64´ 20´

34. Ejemplo F: F1: F2: 01 09 15 64´ 30´ 15 20´

35. Ejemplo F: F1: F2: 09 15 64´ 30´ 15 20´ 01´

36. Ejemplo F: F1: F2: 09 15 20 64´ 30´ 15 01´

37. Ejemplo F: F1: F2: 09 15 15 20 30´ 01 64´

38. Ejemplo F: F1: F2: 15 30´ 01 09 15 20 64´

39. Ejemplo F: F1: F2: 09 15 20 64´ 01 15 30´

40. Ejemplo F: F1: F2: 01 09 30 15 64´ 20 15

41. Ejemplo F: F1: F2: 01 09 30 15 64´ 20 15

42. Archivos utilizados

43. Código

44. ORDENAMIENTO POR INTERCALACIÓN BALANCEADA

45. Método de Intercalación Balanceada Realizar particiones tomando secuencias ordenadas de máxima longitud en lugar de secuencias ordenadas de tamaño fijo previamente determinadas. La mezcla equilibrada múltiple utiliza m archivos auxiliares, de los que m/2 son de entrada y m/2 de salida. El proceso de mezcla se realiza en una sola fase en lugar de las dos fases (separación, fusión) de los algoritmos mezcla directa y fusión natural.

46. Pasos Distribuir registros del archivo original por tramos en los m/2 primeros archivos auxiliares. A continuación, estos se consideran archivos de entrada. Mezclar tramos de los m/2 archivos de entrada y escribirlos consecutivamente en los m/2 archivos de salida. Cambiar la finalidad de los archivos, los de entrada pasan a ser de salida y viceversa; repetir a partir del segundo paso hasta que quede un único tramo, entonces la secuencia está ordenada.

47. Ejemplo 15 3 18 7 18 9 19 9 7 1 3 7 19 15 9 18 18

48. Ejemplo 9 7 1 3 7 19 15 9 9 18 18 7 1

49. 1 7 9 3 7 18 9 19 18 15 3 7 19 15 9 9 18 18 7 1 Inactivo Inactivo Inactivo

50. 1 7 9 3 7 18 9 19 18 15 1 3 9 7 15 9 18 18 19 7

51. Archivos Utilizados

52. Interfaz de código

53. Interfaz de código

54. Interfaz de código

55. ORDENAMIENTO POR INTERCALACIÓN POLIFÁSICA

56. Método Ordenamiento Polifásico En este método podemos ordenar “n” registros en m archivos auxiliares m-1 Archivos de entrada 1 Archivo de Salida Archivos de Entrada: Los archivos de entrada son aquellos que contendrán la información para realizar el ordenamiento Archivos de Salida: Los archivos de Salida son aquellos en donde se guardarán los registros.

57. Ejemplo de Mezcla Polifásica Datos Esenciales Número de Archivos Auxiliares : 3 ---> m 2 Archivos de Entrada ---> m - 1 1 Archivo de Salida ---> Restante Salida Salida Entrada

58. Proceso 1 Distribución de los Registros El primer paso para realizar el ordenamiento es la de distribución de los registros del “ArchivoOriginal” a los archivos auxiliares que posteriormente entrada . Con ello conseguimos 2 objetivos El distribuir los registros del “ArchivoOriginal” a los archivos auxiliares que posteriormente serán de entrada, de forma no uniforme Obtener el número de tramos para realizar el ordenamiento. Para este ejemplo en concreto supongamos que el número de Tramos sea 55

59. Paso 2 Proceso 34 21 Archivos de Entrada Archivos de Salida 13 21 Archivos de Entrada Archivos de Salida

60. Proceso 13 21 Archivos de Entrada Archivos de Salida 8 13 Archivos de Entrada Archivos de Salida

61. Proceso 13 8 Archivos de Entrada Archivos de Salida 5 8 Archivos de Entrada Archivos de Salida

62. Proceso 5 8 Archivos de Entrada Archivos de Salida 3 5 Archivos de Entrada Archivos de Salida

63. Proceso 5 3 Archivos de Entrada Archivos de Salida 2 3 Archivos de Entrada Archivos de Salida

64. Proceso 2 3 Archivos de Entrada Archivos de Salida 1 2 Archivos de Entrada Archivos de Salida

65. Proceso 2 1 Archivos de Entrada Archivos de Salida 1 1 Archivos de Entrada Archivos de Salida