5.7. El ordenamiento burbuja¶
El ordenamiento burbuja hace múltiples pasadas a lo largo de una lista. Compara los ítems adyacentes e intercambia los que no están en orden. Cada pasada a lo largo de la lista ubica el siguiente valor más grande en su lugar apropiado. En esencia, cada ítem “burbujea” hasta el lugar al que pertenece.
La Figura 1 muestra la primera pasada de un ordenamiento burbuja. Los ítems sombreados se comparan para ver si no están en orden. Si hay n ítems en la lista, entonces hay \(n-1\) parejas de ítems que deben compararse en la primera pasada. Es importante tener en cuenta que, una vez que el valor más grande de la lista es parte de una pareja, éste avanzará continuamente hasta que la pasada se complete.
Figura 1: La primera pasada de ordenamientoBurbuja¶
Figura 1: La primera pasada de ordenamientoBurbuja
Al comienzo de la segunda pasada, el valor más grande ya está en su lugar. Quedan \(n-1\) ítems por ordenar, lo que significa que habrá \(n-2\) parejas. Puesto que cada pasada ubica al siguiente valor mayor en su lugar, el número total de pasadas necesarias será \(n-1\). Después de completar la pasada \(n-1\), el ítem más pequeño debe estar en la posición correcta sin requerir procesamiento adicional. El ActiveCode 1 muestra la función ordenamientoBurbuja completa. La función recibe la lista como un parámetro, y lo modifica intercambiando ítems según sea necesario.
La operación de intercambio es ligeramente diferente en Python que en la mayoría de los otros lenguajes de programación. Normalmente, el intercambio de dos ítems en una lista requiere una ubicación de almacenamiento temporal (una ubicación de memoria adicional). Un fragmento de código como
temp = unaLista[i]
unaLista[i] = unaLista[j]
unaLista[j] = temp
intercambiará los ítems \(i\)-ésimo y \(j\)-ésimo de la lista. Sin el almacenamiento temporal, uno de los valores sería sobrescrito.
En Python es posible realizar la asignación simultánea. La instrucción a,b=b,a dará lugar a que se realicen dos instrucciones de asignación al mismo tiempo (véase la Figura 2). Usando la asignación simultánea, la operación de intercambio se puede hacer en una sola instrucción.
Las líneas 5-7 en el ActiveCode 1 realizan el intercambio de los ítems \(i\)-ésimo e \((i+1)\)-ésimo utilizando el procedimiento de tres pasos descrito anteriormente. Note que también podríamos haber utilizado la asignación simultánea para intercambiar los ítems.
Figura 2: Intercambio de dos valores en Python¶
Figura 2: Intercambio de dos valores en Python
El siguiente ejemplo de ActiveCode muestra la función ordenamiento Burbuja completa operando sobre la lista mostrada arriba.
La siguiente animación muestra a ordenamientoBurbuja en acción.
Para analizar el ordenamiento burbuja, debemos tener en cuenta que independientemente de cómo están dispuestos los ítems en la lista inicial, se harán \(n-1\) pasadas para ordenar una lista de tamaño n. La Tabla 1 muestra el número de comparaciones para cada pasada. El número total de comparaciones es la suma de los primeros \(n-1\) enteros. Recuerde que la suma de los primeros n números enteros es \(\frac{1}{2}n^{2} + \frac{1}{2}n\). La suma de los primeros n-1 enteros es \(\frac{1}{2}n^{2} + \frac{1}{2}n - n\), que es igual a \(\frac{1}{2}n^{2} - \frac{1}{2}n\). Esto es todavía \(O(n^{2})\) comparaciones. En el mejor de los casos, si la lista ya está ordenada, no se realizarán intercambios. Sin embargo, en el peor de los casos, cada comparación causará un intercambio. En promedio, intercambiamos la mitad de las veces.
Pasadas |
Comparaciones |
|---|---|
1 |
\(n-1\) |
2 |
\(n-2\) |
3 |
\(n-3\) |
… |
… |
\(n-1\) |
\(1\) |
Un ordenamiento burbuja se considera frecuentemente como el método de ordenamiento más ineficiente ya que debe intercambiar ítems antes de que se conozca su ubicación final. Estas operaciones de intercambio “desperdiciadas” son muy costosas. Sin embargo, debido a que el ordenamiento burbuja hace pasadas por toda la parte no ordenada de la lista, tiene la capacidad de hacer algo que la mayoría de los algoritmos de ordenamiento no pueden. En particular, si durante una pasada no hubo intercambios, entonces sabemos que la lista ya debe estar ordenada. Un ordenamiento burbuja se puede modificar para detenerse anticipadamente si encuentra que la lista ya ha sido ordenada. Esto significa que para las listas que requieran sólo unas pocas pasadas, un ordenamiento burbuja puede tener la ventaja de reconocer que la lista ya está ordenada y se detendrá. El ActiveCode 2 muestra esta modificación, que a menudo se conoce como el ordenamiento burbuja corto.
Autoevaluación
- [1, 9, 19, 7, 3, 10, 13, 15, 8, 12]
- Esta respuesta representa tres intercambios. Una pasada implica que usted continúa haciendo intercambios hasta el final de la lista.
- [1, 3, 7, 9, 10, 8, 12, 13, 15, 19]
- Muy bien
- [1, 7, 3, 9, 10, 13, 8, 12, 15, 19]
- Un ordenamiento burbuja continúa intercambiando números hasta la posición del índica numPasada. Pero recuerde que numPasada comienza con el valor de la longitud de la lista - 1.
- [1, 9, 19, 7, 3, 10, 13, 15, 8, 12]
- Usted ha estado haciendo un ordenamiento por inserción, no un ordenamiento burbuja.
Q-4: Suponga que usted tiene que ordenar la siguiente lista de números: [19, 1, 9, 7, 3, 10, 13, 15, 8, 12]. ¿Cuál de las siguientes listas representa la lista parcialmente ordenada tras tres pasadas completas del ordenamiento burbuja?