Página 2 de 5
1. Descripción.
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?
2. Pseudocódigo en C.
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;
3. Un ejemplo
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
4. Optimizando.
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++)
-
Puede ser que los datos queden ordenados antes de completar el ciclo externo.
Podemos modificar el algoritmo para que verifique si se han realizado
intercambios. Si no se han hecho entonces terminamos con la ejecución, pues eso
significa que los datos ya están ordenados. Te dejo como tarea que modifiques
el algoritmo para hacer esto :-).
-
Otra forma es ir guardando la última posición en que se hizo un intercambio, y
en la siguiente pasada sólo comparar hasta antes de esa posición.
5. Análisis del algoritmo.
Éste es el análisis para la versión no optimizada del algoritmo:
-
Estabilidad:
Este algoritmo nunca intercambia
registros con claves
iguales. Por lo tanto es estable.
-
Requerimientos de
Memoria: Este algoritmo sólo requiere de una variable adicional para
realizar los intercambios.
-
Tiempo de
Ejecución: El ciclo interno se ejecuta n veces para una lista de
n elementos. El ciclo externo también se ejecuta n veces. Es decir, la
complejidad es n * n = O(n2). El comportamiento del caso
promedio depende del orden de entrada de los datos, pero es sólo un poco mejor
que el del peor caso, y sigue siendo O(n2).
Ventajas:
-
Fácil implementación.
-
No requiere memoria adicional.
Desventajas:
-
Muy lento.
-
Realiza numerosas comparaciones.
-
Realiza numerosos intercambios.
Este algoritmo es uno de los más pobres en rendimiento. Ahora te recomiendo que hagas un
programa y lo pruebes. Si tienes dudas mira el
programa de ejemplo.
|
Comentarios
Suscripción de noticias RSS para comentarios de esta entrada.