Informe







Trabajo Grupal

Laboratorio N° 3.


E.A.P.: Ingeniería de Software
Curso: Algoritmica 3
Profesor: Carlos A. Ruiz De la Cruz Melo
Alumnos:
1) Noriega Yarlequé Héctor
2) Tello Gamarra JorgeLuis
3) Villegas Vilcherres Percy







Laboratorio No 3
1. Encuentre el caso medio, el peor y mejor caso
Complejidad Ordenación por Inserción
CASO MEJOR:
Cuando el array está ordenado. Entoncessólo se hace una comparación en cada paso.
Ej. 15 20 45 60 n=4
En general, para n elementos se hacen (n-1) comparaciones.
Por tanto, complejidad O(n).
CASO PEOR:
Cuando el array está ordenadoinversamente.
Ej. 86 52 45 20 n=4
-> 52 86 45 20
-> 45 52 86 20
-> 20 45 52 86
En general, para n elementos se realizan (n-1) intercambios y (n-1) comparaciones.
Por tanto, O(n2).
CASO MEDIO: Loselementos aparecen de forma aleatoria.
Se puede calcular como la suma de las comparaciones mínimas y máximas dividida entre dos:
((n-1) + n(n-1)/2)/2 = (n2+ (n-2))/4 , por tanto complejidad O(n2).Complejidad Ordenacion Burbuja:


2. Luego implemente ambos algoritmos en C++ y java. Pruebe cada programa tanto con datos ordenados, desordenados aleatoriamente y en sentido inverso y no seolvide para cada caso tomar tiempos.

Ordenacion por Insercion:
Ordenado en forma Descendete:





Ordenado en forma Ascendente:



Desordenado en forma Ascendente:






Desordenado en forma Descendente:Ordenacion Burbuja:
Ordenado en forma Ascendente:




Ordenado en forma Descendente:


Desordenado en forma Ascendente:


Desordenado en forma Descendente:


En C++:
Ordenacion Burbuja Ascendente:Ordenamiento Burbuja Descendente:

3. Después verifique si existe alguna relación entre sus ecuaciones halladas para el caso medio, peor y mejor caso) con los tiempos reales de sus implementacionesen java y C++.

En el caso del método Burbuja: EL tiempo es constante en el peor, medio y mejor caso.

En cambio en el método por inserción: El tiempo en el mejor caso es mucho menor que en el medio...