Ordenamiento Burbuja (Bubblesort)

+Ordenamiento Burbuja (Bubblesort)

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.

2. Pseudocódigo en C.

    1. for (i=1; i

    2.      for j=0 ; 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

Lista a analizar:

4 - 3 - 5 - 2 - 1

Se presentan 5 elementos. Es decir, TAM tomará el valor 5. Comienza comparando el primero con el segundo elemento. 4 es mayor que 3, así que se intercambia. Por lo que quedará:

3 - 4 - 5 - 2 - 1

Ahora se comparará el segundo con el tercero: 4 es menor que 5, así que no se hace nada. Continua con el tercero y el cuarto: 5 es mayor que 2. Intercambia y se obtiene:

3 - 4 - 2 - 5 - 1

Luego se compara el cuarto y el quinto: 5 es mayor que 1. Intercambia nuevamente:

3 - 4 - 2 - 1 - 5

Repitiendo este proceso se va obteniendo los siguientes resultados:

3 - 2 - 1 - 4 - 5

2 - 1 - 3 - 4 - 5

1 - 2 - 3 - 4 - 5

[pic 1]

4. Optimizando.

Se pueden realizar algunos cambios en este algoritmo que pueden mejorar su rendimiento.

• Si se observa bien, se puede notar que en cada pasada a través de la lista un elemento va quedando en su posición final. Se puede evitar hacer comparaciones innecesarias si se disminuye el número. Cambiando el ciclo interno de esta manera:

for (j=0; ji; j++)

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.

+ Ordenamiento por Selección.

1. Descripción.

Este algoritmo consiste en:

• Buscar el elemento más pequeño de la lista.
• Intercambiarlo con el elemento ubicado en la primera posición de la lista.
• Buscar el segundo elemento más pequeño de la lista.
• Intercambiarlo con el elemento que ocupa la segunda posición en la lista.
• Repetir este proceso hasta que se haya ordenado toda la lista.

2. Pseudocódigo en C.

  1. for (i=0; i

  2.      pos_men = Menor (lista, TAM, i);

  3.      temp = lista[i];

  4.      lista[i] = lista [pos_men];

  5.      lista [pos_men] = temp;

...