El algoritmo de la burbuja

El algoritmo de la burbuja

Uno de los algoritmos de ordenación más conocidos es el de la burbuja (bubble sort).

Es el típico que se suele enseñar a nivel académico. Para nada es uno de los más eficientes, pero sí que es muy útil para abordar el proceso a nivel teórico.

La forma de ordenar que tiene se basa en el intercambio de los valores de 2 elementos consecutivos si están en el orden equivocado.

Este método se repite hasta que todos los elementos estén en el orden correcto.

Ejemplo

Supongamos que tenemos una lista de números que queremos ordenar de menor a mayor.

Comenzamos comparando el primer elemento de la lista con el segundo.

Si el primer elemento es más pequeño que el segundo, entonces no hacemos ningún cambio.

Si el primer elemento es más grande que el segundo elemento, intercambiamos los valores de los dos elementos.

A continuación, comparamos el segundo elemento de la lista con el tercero.

Si el segundo elemento es más pequeño que el tercero, al igual que antes, no hacemos ningún cambio.

Si el segundo elemento es más grande que el tercero, intercambiamos los valores de los dos elementos.

Vamos repitiendo lo mismo, vamos.

Continuamos comparando elementos de esta manera hasta que hayamos completado la lista.

Cuando terminemos, volvemos a empezar desde el inicio de la lista, ejecutando el mismo proceso.

Una vez que demos una iteración a la lista y que no se haga ningún cambio, significa que ya hemos finalizado el proceso del algoritmo.

Y sabremos que el elemento más pequeño estará al inicio de la lista y el elemento más grande, al final.

Esta podría ser una implementación del algoritmo:

/**  * O(n²)  */ fun bubbleSort(     array: IntArray ): IntArray {     val tempArray = array.copyOf()     for (i in array.indices) {         for (j in 0 until tempArray.size - 1 - i) {             if (tempArray[j] > tempArray[j + 1]) {                 val aux = tempArray[j]                 tempArray[j] = tempArray[j + 1]                 tempArray[j + 1] = aux             }         }     }     return tempArray }

Y esto un test para comprobar su funcionamiento:

import org.junit.Assert.assertTrue import org.junit.Test  class BubbleSortKtTest {      @Test     fun `check bubbleSort order an array`() {         val array = intArrayOf(             1,             4,             5,             0         )          val sortedArray = bubbleSort(array)          assertTrue(             intArrayOf(                 0,                 1,                 4,                 5             ).contentEquals(sortedArray)         )     } }

Ventajas

El algoritmo de la burbuja es simple de entender y de implementar.

Por lo que es ideal para empezar a trabajar con algoritmos.

Desventajas

Es lento en comparación con otros métodos de ordenamiento.

Uno más eficiente, sería por ejemplo el quicksort.

Puntación Big O

En notación Big O, tendría un rendimiento de O(n2).

Conclusión

Es todo un clásico.

Y un buen punto partida para luego entender y aplicar otro tipo de algoritmos más sofisticados.