702
Capítulo 16 Búsqueda y ordenamiento
Efi ciencia del ordenamiento por inserción
El algoritmo de ordenamiento por inserción también se ejecuta en un tiempo igual a
O(n
2
). Al igual que el
ordenamiento por selección, la implementación del ordenamiento por inserción (líneas 22 a 46 de la fi gura 16.8)
contiene dos ciclos. El ciclo
for
(líneas 27 a 45) itera
datos.length – 1
veces, insertando un elemento en la
posición apropiada en los elementos ordenados hasta ahora. Para los fi nes de esta aplicación,
datos.length – 1
es equivalente a
n – 1 (ya que
datos.length
es el tamaño del arreglo). El ciclo
while
(líneas 36 a 41) itera a través
de los anteriores elementos en el arreglo. En el peor de los casos, el ciclo
while
requerirá
n – 1 comparaciones.
Cada ciclo individual se ejecuta en un tiempo
O(n). En notación Big O, los ciclos anidados indican que debemos
multiplicar el número de comparaciones. Para cada iteración de un ciclo exterior, habrá cierto número de itera-
ciones en el ciclo interior. En este algoritmo, para cada
O(n) iteraciones del ciclo exterior, habrá O(n) iteraciones
del ciclo interior. Al multiplicar estos valores se produce un valor Big O de
O(n
2
).
16.3.3 Ordenamiento por combinación
El
ordenamiento por combinación
es un algoritmo de ordenamiento efi ciente, pero en concepto es más com-
plejo que los ordenamientos de selección y de inserción. Para ordenar un arreglo, el algoritmo de ordenamiento
por combinación lo divide en dos subarreglos de igual tamaño, ordena cada subarreglo y después los combina en
un arreglo más grande. Con un número impar de elementos, el algoritmo crea los dos subarreglos de tal forma
que uno tenga más elementos que el otro.
La implementación del ordenamiento por combinación en este ejemplo es recursiva. El caso base es un arre-
glo con un elemento que, desde luego, está ordenado, por lo que el ordenamiento por combinación regresa de
inmediato en este caso. El paso recursivo divide el arreglo en dos piezas de un tamaño aproximadamente igual,
las ordena en forma recursiva y después combina los dos arreglos ordenados en un arreglo ordenado de mayor
tamaño.
Suponga que el algoritmo ya ha combinado arreglos más pequeños para crear los arreglos ordenados A:
4 10 34 56 77
y B:
5 30 51 52 93
El ordenamiento por combinación combina estos dos arreglos en un arreglo ordenado de mayor tamaño. El ele-
mento más pequeño en A es 4 (que se encuentra en el índice cero de A). El elemento más pequeño en B es 5 (que
Figura 16.9
| La clase
PruebaOrdenamientoInsercion
. (Parte 2 de 2).
despues de pasada 4: 19 42 68 76* 88 54 16 99 54 26
-- -- -- -- --
despues de pasada 5: 19 42 54* 68 76 88 16 99 54 26
-- -- -- -- -- --
despues de pasada 6: 16* 19 42 54 68 76 88 99 54 26
-- -- -- -- -- -- --
despues de pasada 7: 16 19 42 54 68 76 88 99* 54 26
-- -- -- -- -- -- -- --
despues de pasada 8: 16 19 42 54 54* 68 76 88 99 26
-- -- -- -- -- -- -- -- --
despues de pasada 9: 16 19 26* 42 54 54 68 76 88 99
-- -- -- -- -- -- -- -- -- --
Arreglo ordenado:
16 19 26 42 54 54 68 76 88 99
16_MAQ_CAP_16_DEITEL.indd702
4/19/081:29:37AM