7.3 Método de intercalación 171 inda ← inda + 1 sino C[i] ← B[indb] indb ← indb + 1 finsi sino Si (inda > n) entonces !se agotó A C[i] ← B[indb] indb ← indb + 1 sino Si (indb > m) entonces ! se agotó B C[i] ← A[inda] inda ← inda + 1 finsi finsi finsi Escribir (C[i]) finpara fin Se propone verificar paso a paso este algoritmo con los arreglos que se dieron como ejem- plo. 7.3.1 Cantidad de comparaciones efectuadas Puede notarse en el algoritmo que la cantidad de componentes del arreglo ordenado (n+m) se recorre una sola vez, y que el recorrido, cualquiera sea el caso, incluye sólo una comparación por componente. Luego, el orden del algoritmo es n+m, o llamando directamente n a este total de elementos, el orden es n. En cambio, ordenar el arreglo D propuesto al principio, aún empleando Quick sort, insume n log2 n operaciones, es decir log2 n veces más. 7.3.2 Ejemplos adicionales Mejoramiento del método de la burbuja Hemos visto que en términos generales, para ordenar un conjunto de n elementos arbitraria- mente desordenados, el algoritmo de Intercambio o Burbuja, que debe realizar n-1 pasadas, es ineficiente. Sin embargo, si el arreglo de datos ya está parcialmente ordenado, puede ocurrir que quede totalmente ordenado antes de completar todas las pasadas. Si en una pasada el arreglo ya quedó ordenado, el proceso se puede interrumpir allí, ahorrando de esta manera el esfuerzo de las pasadas siguientes. La cuestión entonces es cómo saber si el arreglo quedó ordenado, y la respuesta es: si en una pasada completa no fue necesario intercambiar elementos, quiere decir que ya están en orden. Habrá que introducir entonces en el algoritmo un contador de intercambios, o bien una bandera que tome valor Verdadero si en una pasada no se intercambiaron elementos (arreglo ordenado) o Falso, en caso contrario. Escribimos el pseudocódigo resultante: AlgoritmoBurbuja1 entero n, i, j real V[10000], aux logico ordenado ! bandera para detectar si el arreglo está ordenado