Análisis de Algoritmos
Práctico 4
Ingeniería en Informática
Ejercicio 1
En este ejercicio vamos a realizar el análisis detallado de Bubble sort. Al hacerlo, considerar tanto
las comparaciones como los swapeos como únicas operaciones básicas del algoritmo.
a) Indicar tamaño de la entrada, mejor caso y peor caso.
b) Hallar la función T(n) que cuenta el total de operaciones básicas ejecutadas y luego indicar el
orden del algoritmo en el peor caso.
c) Si el peor y el mejor caso no coinciden, repetir nuevamente lo anterior, pero esta vez para el
mejor caso del algoritmo.
Ejercicio 2
Para este ejercicio, considerar nuevamente tanto las comparaciones como los swapeos como
únicas operaciones básicas de cada algoritmo. En el caso de Insertion Sort, considerar que las tres
asignaciones del bloque for equivalen a un swapeo.
a) Realizar el análisis detallado de Selection sort, repitiendo todos los pasos del ejercicio 1.
b) Realizar el análisis detallado de Insertion sort, repitiendo todos los pasos del ejercicio 1.
c) Comparar la eficiencia de los tres algoritmos simples en el peor caso, estableciendo para qué
valores de n es preferible cada uno. ¿Cuál de los tres es el mejor y cuál es el peor algoritmo?
d) Ídem a la parte anterior, pero ahora comparar la eficiencia de los tres algoritmos en el mejor caso.
Ejercicio 3
El siguiente algoritmo Merge es un algoritmo auxiliar que se utiliza en Merge sort. Lo que hace es
fusionar (mezclar) dos subarreglos ya ordenados en un nuevo arreglo finalmente ordenado. Se
quiere realizar el análisis detallado de este algoritmo. Al realizar el análisis, considerar las
asignaciones a resu como únicas operaciones básicas del algoritmo.
int [] merge (int i, int j, int m, int [] arre)
{
int [] resu = new int [[Link]];
int p = i, q = m + 1, r = i;
/* comienzo a mezclar */
while (p <= m && q <= j)
{
if (arre[p] < arre[q])
{
resu[r] = arre[p];
p++;
}
else
{
resu[r] = arre[q];
q++;
}
r++;
}
/* sigue en la próxima página */
Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
1
2 Análisis de Algoritmos - Práctico 4
/* copio el resto del primer subarreglo */
while (p <= m)
{ resu[r] = arre[p];
p++;
r++;
}
/* copio el resto del segundo subarreglo */
while (q <= j)
{ resu[r] = arre[q];
q++;
r++;
}
return resu;
}
a) Ejecutar manualmente el algoritmo para el siguiente arreglo: [2, 3, 5, 7, 4, 6, 8, 9]. Para esta
parte, considerar i = 0, j = 7, m = 3. ¿Cuántas operaciones básicas se ejecutan en total?
b) Ejecutar manualmente el algoritmo para el siguiente arreglo: [3, 6, 8, 9, 1, 2, 4, 7]. Para esta
parte, considerar i = 0, j = 7, m = 3. ¿Cuántas operaciones básicas se ejecutan en total?
c) Realizar el análisis detallado de este algoritmo. ¿Hay diferencia entre el mejor y el peor caso?
Ejercicio 4
En este ejercicio vamos a realizar el análisis detallado de Merge sort. Al realizar el análisis,
considerar la invocación al algoritmo auxiliar merge como única operación básica del algoritmo.
a) Indicar tamaño de la entrada, mejor caso y peor caso.
b) Plantear la recurrencia asociada a la función T(n) para el peor caso de este algoritmo y
resolverla por algún método adecuado. Calcular el orden del algoritmo según el resultado.
c) Si el peor y el mejor caso no coinciden, repetir la parte anterior para el mejor caso.
Ejercicio 5
El siguiente algoritmo Partición es un algoritmo auxiliar que se utiliza en Quick sort. Lo que hace
es re-ordenar el arreglo, dejando a la izquierda del pivote los valores menores que él y a la derecha
los mayores que él. Como resultado, devuelve la posición del pivote. Se quiere realizar el análisis
detallado de este algoritmo. Al hacerlo, considerar las comparaciones (arre[p] < pivote) y
(arre[q] > pivote) como únicas operaciones básicas del algoritmo.
int particion (int [] arre, int i, int j, int pivote)
{
int p = i, q = j;
do
{ while (arre[p] < pivote)
p++;
while (arre[q] > pivote)
q--;
swap (arre[p], arre[q]);
}
while (p < q);
return p;
}
Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
2
Análisis de Algoritmos – Práctico 4 3
a) Ejecutar manualmente el algoritmo para el siguiente arreglo: [1, 2, 3, 4, 5, 6, 7]. Para esta
parte, considerar i = 0, j = 6, pivote = 4. ¿Cuántas operaciones básicas se ejecutan en total?
b) Ejecutar manualmente el algoritmo para el siguiente arreglo: [7, 6, 5, 4, 3, 2, 1]. Para esta
parte, considerar i = 0, j = 6, pivote = 4. ¿Cuántas operaciones básicas se ejecutan en total?
c) Ejecutar manualmente el algoritmo para el siguiente arreglo: [1, 2, 3, 4, 5, 6, 7]. Para esta
parte, considerar i = 0, j = 6, pivote = 7. ¿Cuántas operaciones básicas se ejecutan en total?
d) Ejecutar manualmente el algoritmo para el siguiente arreglo: [7, 6, 5, 4, 3, 2, 1]. Para esta
parte, considerar i = 0, j = 6, pivote = 7. ¿Cuántas operaciones básicas se ejecutan en total?
e) Realizar el análisis detallado de este algoritmo. ¿Hay diferencia entre el mejor y el peor caso?
Ejercicio 6
En este ejercicio vamos a realizar el análisis detallado de Quick sort. A los efectos del análisis,
suponer que la operación auxiliar buscarPivote es efectivamente de O(1) y por lo tanto puede
despreciarse. Al realizar el análisis, considerar la invocación al algoritmo auxiliar particion
como única operación básica del algoritmo.
a) Indicar tamaño de la entrada, mejor caso y peor caso.
b) Plantear la recurrencia asociada a la función T(n) para el peor caso de este algoritmo y
resolverla por algún método adecuado. Calcular el orden del algoritmo según el resultado.
c) Si el peor y el mejor caso no coinciden, repetir la parte anterior para el mejor caso.
Ejercicio 7
En este ejercicio vamos a probar que ningún algoritmo de ordenación basado en comparaciones
puede tener un orden inferior a n . log (n).
a) Explicar brevemente porqué el árbol de decisión para resolver el problema de sorting es un
árbol binario. ¿Qué representan las hojas y qué representa la altura de este árbol?
b) Definir inductivamente el conjunto de los árboles binarios de elementos de tipo T.
c) Demostrar que si un árbol binario de altura h tiene t hojas, entonces se cumple que log (t) ≤ h.
Sug: realizar la prueba por inducción según la definición inductiva de la parte anterior.
d) Demostrar que log (n!) = Ω (n . log (n)), aplicando la definición de orden inferior vista en el curso.
Sug: probar previamente que log (n!) ≥ (n / 2) . log (n / 2) a partir de un cierto valor para n.
e) Utilizando las partes anteriores, concluir que si T(n) es la cantidad de comparaciones
necesarias para ordenar un arreglo de n elementos, entonces T (n) = Ω (n . log (n)).
Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
3
