Efi ciencia del ordenamiento por combinación
El ordenamiento por combinación es un algoritmo mucho más efi ciente que el de inserción o el de selección.
Considere la primera llamada (no recursiva) al método
ordenarArreglo
. Esto produce dos llamadas recursivas
al método
ordenarArreglo
con subarreglos, cada uno de los cuales tiene un tamaño aproximado de la mitad
del arreglo original, y una sola llamada al método
combinar
. Esta llamada a
combinar
requiere, a lo más,
n – 1
comparaciones para llenar el arreglo original, que es
O(n). (Recuerde que se puede elegir cada elemento en el
arreglo mediante la comparación de un elemento de cada uno de los subarreglos). Las dos llamadas al método
ordenarArreglo
producen cuatro llamadas recursivas más al método
ordenarArreglo
, cada una con un sub-
arreglo de un tamaño aproximado a una cuarta parte del tamaño del arreglo original, junto con dos llamadas
al método
combinar
. Estas dos llamadas al método
combinar
requieren, a lo más,
n/2 – 1 comparaciones para
un número total de
O(n) comparaciones. Este proceso continúa, y cada llamada a
ordenarArreglo
genera dos
llamadas adicionales a
ordenarArreglo
y una llamada a
combinar
, hasta que el algoritmo divide el arreglo en
subarreglos de un elemento. En cada nivel, se requieren
O(n) comparaciones para combinar los subarreglos. Cada
nivel divide el tamaño de los arreglos a la mitad, por lo que al duplicar el tamaño del arreglo se requiere un nivel
más. Si se cuadruplica el tamaño del arreglo, se requieren dos niveles más. Este patrón es logarítmico, y produce
log
2
n niveles. Esto resulta en una efi ciencia total de O(n log n). En la fi gura 16.12 se sintetizan muchos de los
algoritmos de búsqueda y ordenamiento que cubrimos en este libro, y se enlista el valor de Big O para cada uno
de ellos. En la fi gura 16.13 se enlistan los valores de Big O que hemos cubierto en este capítulo, junto con cierto
número de valores para
n, para resaltar las diferencias en las proporciones de crecimiento.
Figura 16.11
| La clase
PruebaOrdenamientoCombinacion
. (Parte 3 de 3).
combinacion: 19 78
23
19 23 78
division: 14 33
14
33
combinacion: 14
33
14 33
combinacion: 19 23 78
14 33
14 19 23 33 78
combinacion: 23 30 48 68 95
14 19 23 33 78
14 19 23 23 30 33 48 68 78 95
Ordenado: 14 19 23 23 30 33 48 68 78 95
Algoritmo
Ubicación
Big O
Algoritmos de búsqueda:
Búsqueda lineal
Búsqueda binaria
Búsqueda lineal recursiva
Búsqueda binaria recursiva
Sección 16.2.1.
Sección 16.2.2.
Ejercicio 16.8.
Ejercicio 16.9.
O(n)
O(log n)
O(n)
O(log n)
Figura 16.12
| Algoritmos de búsqueda y ordenamiento con valores de Big O.
(Parte 1 de 2).
16.3 Algoritmos de ordenamiento
707
16_MAQ_CAP_16_DEITEL.indd707
4/19/081:29:39AM