COMPARACION DE COMPLEJIDAD Y TIEMPO EN ALGORITMOS.

Se analizara el tiempo de ejecución y el tiempo empleado por los algoritmos de inserción directa, selección directa, el método de la burbuja y el método de la burbuja mejorado, ordenando una arreglo de enteros en 3 casos: en orden ascendente (mejor caso), un orden descendente (peor caso) y un orden al azar (caso promedio).

ALGORITMOS:

- INSERCION DIRECTA:

Para x=2 hasta n (+)

Y x-1

Sw 0

Mientras (y<>0) y (sw=0)

Si A[y-1]>A[y]

AuxA[y-1]

A[y-1]A[y]

A[y]Aux

De lo contrario

Sw1

Yy-1

- SELECCIÓN DIRECTA:

Para x=1 hasta n-1 (+)

Menorx

Para y=x+1 hasta n (+)

Si A[y] <A [menor]

Menory

Si menor<>x

AuxA[x]

A[x] A[menor]

A[menor] Aux

- METODO DE LA BURBUJA:

Para i=1 hasta n-1

Para j=i+1 hasta n

Si A[i]>A[j]

AuxA[i]

A[i]A[j]

A[j]Aux

• METODO DE LA BURBUJA MEJORADO:

Sw1

Mientras sw=1

Sw 0

Para i=1 hasta n-1 (+)

Si A[i] >A[i+1]

AuxA[i]

A[i]A[i+1]

A[i+1]Aux

COMPARACION DE COMPLEJIDADES:

TIEMPO EN COMPARACIONES Y ASIGNACIONES:

CONCLUSIONES:

No se podría decir a ciencia cierta cual es el mejor algoritmo de los tres, ya que los tres presentan desventajas con respecto a los otros algoritmos en algunos casos. Pero entre los mejores se encuentran el método de selección directa y el método de la burbuja mejorado, viendo en el mejor caso, el tiempo empleado es el mismo, en el peor caso es mejor el método de selección directa, pero en cuanto su complejidad, el método de la burbuja mejorado le lleva ventaja, ya que para ordenar en el peor de los casos su complejidad es n log n, mientras que el otro es de n2.

En el caso promedio, todos los tiempos varian, por que estos no dependen n, si no que dependen del arreglo, es decir, de la probabilidad que el siguiente numero sea menor o mayor al anterior.

NOMBRE:

CARRERA: LICENCIATURA EN COMPUTACION.

SEMESTRE: IV.

LUNES 10 DE MARZO DEL 2002.