Análisis y Diseño de Algoritmos
Prof:
Ing. Victor Garro
Asistente: Marco Elizondo
Vargas
ORDENAMIENTOS
Ordenamiento
burbuja
Este es el algoritmo más sencillo probablemente. Ideal para empezar.
Consiste en ciclar repetidamente a través de la lista, comparando elementos
adyacentes de dos en dos. Si un elemento es mayor que el que está en la
siguiente posición se intercambian. ¿Sencillo no?
Tabla
de variables |
||
Nombre |
Tipo |
Uso |
lista |
Cualquiera |
Lista a ordenar |
TAM |
Constante entera |
Tamaño de la lista |
i |
Entero |
Contador |
j |
Entero |
Contador |
temp |
El mismo que los elementos de la lista |
Para realizar los intercambios |
1. for (i=1; i<TAM; i++)
2. for j=0 ; j<TAM - 1; j++)
3. if (lista[j] > lista[j+1])
4. temp = lista[j];
5. lista[j] = lista[j+1];
6. lista[j+1] = temp;
Vamos a ver un ejemplo. Esta es nuestra lista:
4 - 3 - 5 - 2 - 1
Tenemos 5 elementos. Es decir, TAM toma el valor 5. Comenzamos comparando el
primero con el segundo elemento. 4 es mayor que 3, así que intercambiamos.
Ahora tenemos:
3 - 4 - 5 - 2 - 1
Ahora comparamos el segundo con el tercero: 4 es menor que 5, así que no
hacemos nada. Continuamos con el tercero y el cuarto: 5 es mayor que 2.
Intercambiamos y obtenemos:
3 - 4 - 2 - 5 - 1
Comparamos el cuarto y el quinto: 5 es mayor que 1. Intercambiamos
nuevamente:
3 - 4 - 2 - 1 - 5
Repitiendo este proceso vamos obteniendo los siguientes resultados:
3 - 2 - 1 - 4 - 5
2 - 1 - 3 - 4 - 5
1 - 2 - 3 - 4 - 5
Se pueden realizar algunos cambios en este algoritmo que pueden mejorar su
rendimiento.
·
Si observas bien, te darás cuenta que en cada
pasada a través de la lista un elemento va quedando en su posición final. Si no
te queda claro mira el ejemplo de arriba. En la primera pasada el 5 (elemento
mayor) quedó en la última posición, en la segunda el 4 (el segundo mayor
elemento) quedó en la penúltima posición. Podemos evitar hacer comparaciones
innecesarias si disminuimos el número de éstas en cada pasada. Tan sólo hay que
cambiar el ciclo interno de esta manera:
for (j=0; j<TAM - i; j++)
Éste es el análisis para la versión no optimizada del algoritmo:
Ventajas:
Desventajas: