712

Capítulo 16 Búsqueda y ordenamiento

Ejercicios

16.5

(Ordenamiento de burbuja) Implemente el ordenamiento de burbuja, otra técnica de ordenamiento simple, 

pero inefi ciente. Se le llama ordenamiento de burbuja o de hundimiento, debido a que los valores más pequeños van 
“subiendo como burbujas” gradualmente, hasta llegar a la parte superior del arreglo (es decir, hacia el primer elemento) 
como las burbujas de aire que se elevan en el agua, mientras que los valores más grandes se hunden en el fondo (fi nal) 
del arreglo. Esta técnica utiliza ciclos anidados para realizar varias pasadas a través del arreglo. Cada pasada compara 
pares sucesivos de elementos. Si un par se encuentra en orden ascendente (o los valores son iguales), el ordenamiento de 
burbuja deja los valores como están. Si un par se encuentra en orden descendente, el ordenamiento de burbuja inter-
cambia sus valores en el arreglo.

En la primera pasada se comparan los primeros dos elementos del arreglo, y se intercambian sus valores si es nece-

sario. Después se comparan los elementos segundo y tercero en el arreglo. En la pasada fi nal, se comparan los últimos 
dos elementos en el arreglo y se intercambian, en caso de ser necesario. Después de una pasada, el elemento más grande 
estará en el último índice. Después de dos pasadas, los dos elementos más grandes se encontrarán en los últimos dos 
índices. Explique por qué el ordenamiento de burbuja es un algoritmo 

O(n

2

).

16.6

(Ordenamiento de burbuja mejorado) Realice las siguientes modifi caciones simples para mejorar el rendimiento 

del ordenamiento de burbuja que desarrolló en el ejercicio 16.5:
 

a) Después de la primera pasada, se garantiza que el número más grande estará en el elemento con la numera-

ción más alta del arreglo; después de la segunda pasada, los dos números más altos estarán “acomodados”; 
y así en lo sucesivo. En vez de realizar nueve comparaciones en cada pasada, modifi que el ordenamiento de 
burbuja para que realice ocho comparaciones en la segunda pasada, siete en la tercera, y así en lo sucesivo.

 

b) Los datos en el arreglo tal vez se encuentren ya en el orden apropiado, o casi apropiado, así que ¿para qué 

realizar nueve pasadas, si basta con menos? Modifi que el ordenamiento para comprobar al fi nal de cada 
pasada si se han realizado intercambios. Si no se ha realizado ninguno, los datos ya deben estar en el orden 
apropiado, por lo que el programa debe terminar. Si se han realizado intercambios, por lo menos, se necesita 
una pasada más.

16.7

(Ordenamiento de cubeta) Un ordenamiento de burbuja comienza con un arreglo unidimensional de ente-

ros positivos que se deben ordenar, y un arreglo bidimensional de enteros, en el que las fi las están indexadas de 0 a 9 y 
las columnas de 0 a 

n – 1, en donde n es el número de valores a ordenar. Cada fi la del arreglo bidimensional se conoce 

como una 

cubeta. Escriba una clase llamada 

OrdenamientoCubeta

, que contenga un método llamado 

ordenar

 y que 

opere de la siguiente manera:
 

a) Coloque cada valor del arreglo unidimensional en una fi la del arreglo de cubeta, con base en el dígito de las 

unidades (el de más a la derecha) del valor. Por ejemplo, el número 97 se coloca en la fi la 7, el 3 se coloca 
en la fi la 3 y el 100 se coloca en la fi la 0. A este procedimiento se le llama 

pasada de distribución.

 

b) Itere a través del arreglo de cubeta fi la por fi la, y copie los valores de vuelta al arreglo original. A este proce-

dimiento se le llama 

pasada de recopilación. El nuevo orden de los valores anteriores en el arreglo unidimen-

sional es 100, 3 y 97.

 

c) Repita este proceso para cada posición de dígito subsiguiente (decenas, centenas, miles, etcétera). En la 

segunda pasada (el dígito de las decenas) se coloca el 100 en la fi la 0, el 3 en la fi la 0 (ya que 3 no tiene dígito 
de decenas) y el 97 en la fi la 9. Después de la pasada de recopilación, el orden de los valores en el arreglo 
unidimensional es 100, 3 y 97. En la tercera pasada (dígito de las centenas), el 100 se coloca en la fi la 1, 
el 3 en la fi la 0 y el 97 en la fi la 0 (después del 3). Después de esta última pasada de recopilación, el arreglo 
original se encuentra en orden.

Observe que el arreglo bidimensional de cubetas es 10 veces la longitud del arreglo entero que se 

está ordenando. Esta técnica de ordenamiento proporciona un mejor rendimiento que el ordenamiento 
de burbuja, pero requiere mucha más memoria; el ordenamiento de burbuja requiere espacio sólo para 
un elemento adicional de datos. Esta comparación es un ejemplo de la concesión entre espacio y tiempo: 
el ordenamiento de cubeta utiliza más memoria que el ordenamiento de burbuja, pero su rendimiento es 
mejor. Esta versión del ordenamiento de cubeta requiere copiar todos los datos de vuelta al arreglo original 
en cada pasada. Otra posibilidad es crear un segundo arreglo de cubeta bidimensional, e intercambiar en 
forma repetida los datos entre los dos arreglos de cubeta.

16.8

(Búsqueda lineal recursiva) Modifi que la fi gura 16.2 para utilizar el método recursivo 

busquedaLinealRecur-

siva

 para realizar una búsqueda lineal en el arreglo. El método debe recibir la clave de búsqueda y el índice inicial como 

16_MAQ_CAP_16_DEITEL.indd712

4/19/081:29:41AM