Seguimiento Merge Sort
•Download as PPT, PDF•
0 likes•819 views
Seguimiento del MergeSort que hicimos dani y yo en tecnicas :)
![Merge (vector,0,0,1);
1572
void Merge(int A[], int inicio, int mitad, int final )
{
k = 0;
i = inicio;
j = mitad + 1;
n = final – inicio;
while( i < mitad + 1 )&&( j < final + 1 )
{
if ( A[i] < A[j] )
{
B[k] = A[i];
i = i + 1;
}
else
{
B[k] = A[j];
j = j + 1;
}
k = k + 1;
} //Continuara…
Inicio=0
Mitad=0
Final=1
VARIABLES](https://image.slidesharecdn.com/seguimientomergesort-090414111031-phpapp01/85/Seguimiento-Merge-Sort-33-320.jpg)
Seguimiento Merge Sort
- 3. 15 10 612472 39 5843
- 4. 15 10 612472 39 5843
- 5. 15 10 612472 39 5843 MergeSort(vector,0,7);
- 6. 15 10 612472 39 5843 MergeSort(vector,0,7);
- 7. 15 10 612472 39 5843 MergeSort(vector,0,7); Inicio=0 Final=7 VARIABLES FINAL>INCIO
- 8. 15 10 612472 39 5843 MergeSort(vector,0,7); VARIABLES FINAL>INCIO
- 9. 15 10 612472 39 5843 MergeSort(vector,0,7); VARIABLES Se cumple FINAL>INCIO
- 10. 15 10 612472 39 5843 MergeSort(vector,0,7); VARIABLES Se cumple FINAL>INCIO
- 11. 15 10 612472 39 5843 MergeSort(vector,0,3); 15 2472 43 39 5810 61 MergeSort(vector,4,7);
- 12. 15 10 612472 39 5843 MergeSort(vector,0,3); 15 2472 43 Inicio=0 Inicio=4 Final=3 Final=7 VARIABLES FINAL>INCIO MergeSort(vector,4,7); 39 5810 61
- 13. 15 10 612472 39 5843 MergeSort(vector,0,3); 15 2472 43 Inicio=0 Inicio=4 Final=3 Final=7 Mitad=1 VARIABLES FINAL>INCIO MergeSort(vector,4,7); 39 5810 61
- 14. 15 10 612472 39 5843 MergeSort(vector,0,3); 15 2472 43 Inicio=0 Inicio=4 Final=3 Final=7 Mitad=1 Mitad=5 VARIABLES FINAL>INCIO MergeSort(vector,4,7); 39 5810 61
- 15. 15 10 612472 39 5843 MergeSort(vector,0,3); 15 2472 43 Inicio=0 Inicio=4 Final=3 Final=7 Mitad=1 Mitad=5 VARIABLES Se cumple Se cumple FINAL>INCIO MergeSort(vector,4,7); 39 5810 61
- 16. 15 10 612472 39 5843 MergeSort(vector,0,3); 15 2472 43 Inicio=0 Inicio=4 Final=3 Final=7 Mitad=1 Mitad=5 VARIABLES Se cumple Se cumple FINAL>INCIO MergeSort(vector,4,7); 39 5810 61
- 17. 15 10 612472 39 5843 MergeSort(vector,0,1); 15 2472 43 MergeSort(vector,2,3); 39 5810 61 MergeSort(vector,4,5); MergeSort(vector,6,7); 1572 2443 3910 5861
- 18. 15 10 612472 39 5843 MergeSort(vector,0,1); 15 2472 43 Inicio=0 Inicio=2 Final=1 Final=3 Inicio=4 Inicio=6 Final=5 Final=7 VARIABLES FINAL>INCIO MergeSort(vector,2,3); 39 5810 61 MergeSort(vector,4,5); MergeSort(vector,6,7); 1572 2443 3910 5861
- 19. 15 10 612472 39 5843 MergeSort(vector,0,1); 15 2472 43 Inicio=0 Inicio=2 Final=1 Final=3 Inicio=4 Inicio=6 Final=5 Final=7 VARIABLES FINAL>INCIO MergeSort(vector,2,3); 39 5810 61 MergeSort(vector,4,5); MergeSort(vector,6,7); 1572 2443 3910 5861
- 20. 15 10 612472 39 5843 MergeSort(vector,0,1); 15 2472 43 Inicio=0 Inicio=2 Final=1 Final=3 Mitad=0 Mitad=2 Inicio=4 Inicio=6 Final=5 Final=7 Mitad=4 Mitad=6 VARIABLES FINAL>INCIO MergeSort(vector,2,3); 39 5810 61 MergeSort(vector,4,5); MergeSort(vector,6,7); 1572 2443 3910 5861
- 21. 15 10 612472 39 5843 MergeSort(vector,0,1); 15 2472 43 Inicio=0 Inicio=2 Final=1 Final=3 Mitad=0 Mitad=2 Inicio=4 Inicio=6 Final=5 Final=7 Mitad=4 Mitad=6 VARIABLES Se cumple Se cumple Se cumple Se cumple FINAL>INCIO MergeSort(vector,2,3); 39 5810 61 MergeSort(vector,4,5); MergeSort(vector,6,7); 1572 2443 3910 5861
- 22. 15 10 612472 39 5843 MergeSort(vector,0,1); 15 2472 43 Inicio=0 Inicio=2 Final=1 Final=3 Mitad=0 Mitad=2 Inicio=4 Inicio=6 Final=5 Final=7 Mitad=4 Mitad=6 VARIABLES Se cumple Se cumple Se cumple Se cumple FINAL>INCIO MergeSort(vector,2,3); 39 5810 61 MergeSort(vector,4,5); MergeSort(vector,6,7); 1572 2443 3910 5861
- 23. 15 10 612472 39 5843 MergeSort(vector,0,0); 15 2472 43 MergeSort(vector,1,1); 39 5810 61 MergeSort(vector,2,2); MergeSort(vector,3,3); MergeSort(vector,4,4); MergeSort(vector,5,5); MergeSort(vector,6 ,6); MergeSort(vector,7,7); 1572 2443 3910 5861 72 15 43 24 10 39 61 58
- 24. 15 10 612472 39 5843 15 2472 43 Inicio=0 Inicio=1 Final=0 Final=1 Inicio=2 Inicio=3 Final=2 Final=3 Inicio=4 Inicio=5 Final=4 Final=5 Inicio=6 Inicio=7 Final=6 Final=7 VARIABLES FINAL>INCIO 39 5810 61 1572 1572 1572 1572 72 15 43 24 10 39 61 58 MergeSort(vector,0,0); MergeSort(vector,1,1); MergeSort(vector,2,2); MergeSort(vector,3,3); MergeSort(vector,4,4); MergeSort(vector,5,5); MergeSort(vector,6 ,6); MergeSort(vector,7,7);
- 25. 15 10 612472 39 5843 15 2472 43 Inicio=0 Inicio=1 Final=0 Final=1 Inicio=2 Inicio=3 Final=2 Final=3 Inicio=4 Inicio=5 Final=4 Final=5 Inicio=6 Inicio=7 Final=6 Final=7 VARIABLES FINAL>INCIO 39 5810 61 1572 1572 1572 1572 72 15 43 24 10 39 61 58 MergeSort(vector,0,0); MergeSort(vector,1,1); MergeSort(vector,2,2); MergeSort(vector,3,3); MergeSort(vector,4,4); MergeSort(vector,5,5); MergeSort(vector,6 ,6); MergeSort(vector,7,7);
- 26. 15 10 612472 39 5843 15 2472 43 Inicio=0 Inicio=1 Final=0 Final=1 Mitad=0 Mitad=1 Inicio=2 Inicio=3 Final=2 Final=3 Mitad=2 Mitad=3 Inicio=4 Inicio=5 Final=4 Final=5 Mitad=4 Mitad=5 Inicio=6 Inicio=7 Final=6 Final=7 Mitad=6 Mitad=7 VARIABLES FINAL>INCIO 39 5810 61 1572 1572 1572 1572 72 15 43 24 10 39 61 58 MergeSort(vector,0,0); MergeSort(vector,1,1); MergeSort(vector,2,2); MergeSort(vector,3,3); MergeSort(vector,4,4); MergeSort(vector,5,5); MergeSort(vector,6 ,6); MergeSort(vector,7,7);
- 27. 15 10 612472 39 5843 15 2472 43 Inicio=0 Inicio=1 Final=0 Final=1 Mitad=0 Mitad=1 Inicio=2 Inicio=3 Final=2 Final=3 Mitad=2 Mitad=3 Inicio=4 Inicio=5 Final=4 Final=5 Mitad=4 Mitad=5 Inicio=6 Inicio=7 Final=6 Final=7 Mitad=6 Mitad=7 VARIABLES No se cumple No se cumple No se cumple No se cumple No se cumple No se cumple No se cumple No se cumple FINAL>INCIO 39 5810 61 1572 1572 1572 1572 72 15 43 24 10 39 61 58 MergeSort(vector,0,0); MergeSort(vector,1,1); MergeSort(vector,2,2); MergeSort(vector,3,3); MergeSort(vector,4,4); MergeSort(vector,5,5); MergeSort(vector,6 ,6); MergeSort(vector,7,7);
- 28. 15 10 612472 39 5843 15 2472 43 Inicio=0 Inicio=1 Final=0 Final=1 Mitad=0 Mitad=1 Inicio=2 Inicio=3 Final=2 Final=3 Mitad=2 Mitad=3 Inicio=4 Inicio=5 Final=4 Final=5 Mitad=4 Mitad=5 Inicio=6 Inicio=7 Final=6 Final=7 Mitad=6 Mitad=7 VARIABLES No se cumple No se cumple No se cumple No se cumple No se cumple No se cumple No se cumple No se cumple FINAL>INCIO 39 5810 61 1572 1572 1572 1572 72 15 43 24 10 39 61 58 MergeSort(vector,0,0); MergeSort(vector,1,1); MergeSort(vector,2,2); MergeSort(vector,3,3); MergeSort(vector,4,4); MergeSort(vector,5,5); MergeSort(vector,6 ,6); MergeSort(vector,7,7);
- 29. 15 10 612472 39 5843 MergeSort(vector,0,1); 15 2472 43 Inicio=0 Inicio=2 Final=1 Final=3 Mitad=0 Mitad=2 Inicio=4 Inicio=6 Final=5 Final=7 Mitad=4 Mitad=6 VARIABLES Se cumple Se cumple Se cumple Se cumple FINAL>INCIO MergeSort(vector,2,3); 39 5810 61 MergeSort(vector,4,5); MergeSort(vector,6,7); 1572 2443 3910 5861
- 30. 15 10 612472 39 5843 MergeSort(vector,0,1); 15 2472 43 Inicio=0 Inicio=2 Final=1 Final=3 Mitad=0 Mitad=2 Inicio=4 Inicio=6 Final=5 Final=7 Mitad=4 Mitad=6 VARIABLES Se cumple Se cumple Se cumple Se cumple FINAL>INCIO MergeSort(vector,2,3); 39 5810 61 MergeSort(vector,4,5); MergeSort(vector,6,7); 1572 2443 3910 5861
- 31. 15 10 612472 39 5843 MergeSort(vector,0,1); 15 2472 43 Inicio=0 Inicio=2 Final=1 Final=3 Mitad=0 Mitad=2 Inicio=4 Inicio=6 Final=5 Final=7 Mitad=4 Mitad=6 VARIABLES Se cumple Se cumple Se cumple Se cumple FINAL>INCIO MergeSort(vector,2,3); 39 5810 61 MergeSort(vector,4,5); MergeSort(vector,6,7); 1572 2443 3910 5861
- 32. 15 10 612472 39 5843 MergeSort(vector,0,1); 15 2472 43 Inicio=0 Inicio=2 Final=1 Final=3 Mitad=0 Mitad=2 Inicio=4 Inicio=6 Final=5 Final=7 Mitad=4 Mitad=6 VARIABLES Se cumple Se cumple Se cumple Se cumple FINAL>INCIO MergeSort(vector,2,3); 39 5810 61 MergeSort(vector,4,5); MergeSort(vector,6,7); 1572 2443 3910 5861
- 33. Merge (vector,0,0,1); 1572 void Merge(int A[], int inicio, int mitad, int final ) { k = 0; i = inicio; j = mitad + 1; n = final – inicio; while( i < mitad + 1 )&&( j < final + 1 ) { if ( A[i] < A[j] ) { B[k] = A[i]; i = i + 1; } else { B[k] = A[j]; j = j + 1; } k = k + 1; } //Continuara… Inicio=0 Mitad=0 Final=1 VARIABLES
- 78. 7215
- 79. 7215
- 80. 15 10 612472 39 5843 15 2472 43 39 5810 61 7215 2443 3910 5861
- 81. 15 10 612472 39 5843 15 2472 43 39 5810 61 7215 2443 3910 5861
- 82. 15 10 612472 39 5843 15 2472 43 39 5810 61 7215 2443 3910 5861
- 83. 15 10 612472 39 5843 15 2472 43 39 5810 61 7215 2443 3910 5861 24 43 10 39 58 61
- 84. 15 10 612472 39 5843 15 2472 43 39 5810 61 7215 4324 3910 6158
- 85. 15 10 612472 39 5843 15 2472 43 39 5810 61 7215 4324 3910 6158
- 86. 72 10 584315 39 6124 72 4315 24 39 6110 58 7215 4324 3910 6158
- 87. 72 10 584315 39 6124 72 4315 24 39 6110 58
- 88. 72 10 584315 39 6124 72 4315 24 39 6110 58
- 89. 24 7215 43 39 6110 58 72 10 584315 39 6124 72 4315 24 39 6110 58
- 90. 72 10 584315 39 6124 24 7215 43 39 6110 58
- 91. 24 10 587215 39 6143 24 7215 43 39 6110 58
- 92. 15 10 612472 39 5843
- 93. 15 10 612472 39 5843 MergeSort(vector,0,7);
- 94. 15 10 612472 39 5843 MergeSort(vector,0,7);
- 95. 15 10 612472 39 5843 MergeSort(vector,0,7);
- 96. 15 10 612472 39 5843 MergeSort(vector,0,7); 15 43 613910 58 7224
- 97. 15 43 613910 58 7224 MergeSort(vector,0,7);
- 98. 15 43 613910 58 7224
- 99. 15 43 613910 58 7224 