Bubble sort

Bubble sort (ordenamiento burbuja) es un método bastante sencillo e intuitivo de ordenar datos. Es muy útil para comenzar a comprender las formas en las que podemos ordenar la información, aunque dada su complejidad no es muy útil en casos muy demandantes.

• Idea del funcionamiento
• Implementación
• Complejidad

Idea del funcionamiento

Para poder entender cómo funciona el algoritmo, usaremos el conjunto desordenado de datos 7, 9, 3, 4, 8 y definiremos como \(N\) la cantidad de datos a ordenar, en este ejemplo \(N=6\).

La forma en la que funciona el algoritmo del Bubble sort es utilizando intercambios. Por ejemplo, si queremos ordenar los datos de forma creciente, sabemos que hemos de dejar al principio (lado izquierdo) los valores más pequeños. Entonces vamos “tomando” pares de datos y dejando del lado izquierdo el valor más pequeño. Para esto intercambiamos las posiciones de los dos elementos en cuestión, y dejamos en la posición de la izquierda el valor más chico, y en el de la derecha el más grande. En base a nuestro ejemplo sería:

Como podrás notar, para nuestro conjunto de \(N\) datos, hemos realizado a penas \(N-1\) movimientos y hemos llegado al final de los pares, pero el conjunto aún no está del todo ordenado, entonces habrá que realizar otra vez el algoritmo, comenzando por el primer par de nuevo. Es importante notar también, que después de haber recorrido todos los datos una vez, al final quedará el más grande de los datos en el extremo derecho, dado que siempre se habrá movido a la derecha con respecto al resto.

Aquí ya hemos terminado otra vez con todos nuestros pares, y afortunadamente el conjunto ha quedado ordenado, sin embargo, dos repeticiones no habrían bastado para el conjunto 9, 8, 7, 6, 5.

Puedes observar el algoritmo en acción con la siguiente animación:

Implementación

La implementación del Bubble sort en C++ es bastante sencilla

Nota que estamos haciendo el recorrido de todos los pares una vez por cada dato del conjunto, esto es para asegurarnos de que al final todo quede bien ordenado. Es importante notar además, que con conjunto[j + 1] nos referimos al siguiente elemento, contiguo a conjunto[j] y que debido a esto se hace una corrección en el límite del ciclo interior, al hacerlo hasta j < N -1 y así evitar salir del arreglo.

Complejidad

Dado que estamos realizando \(N\) recorridos por cada dato y son \(N\) datos, entonces podemos decir que la complejidad del algoritmo de ordenamiento bubble sort es \(O(n^2)\). Recuerda que cuando hablamos de complejidad tomamos el peor de los casos posibles, y se “redondea” al factor que tiene la tasa de crecimiento mayor.

Es sencillo notar que se pueden hacer algunas mejoras al algoritmo, se puede optimizar de varias maneras, de cualquier forma, para un caso muy grande, como \(100000\) de datos, obtendremos un desempeño muy cercano al \(O(n^2)\). Debido a esto, el algoritmo puede ser útil como explicación general de un algoritmo de ordenamiento, dado que es sencillo de entender y sencillo de codificar, pero resulta ser poco práctico para resolver problemas en los que se manejen grandes conjuntos de datos.

Cita esta página

Include Poetry - Code. (2020, 4 de enero). Bubble sort. Obtenido de https://www.include-poetry.com/Code/C++/Metodos/Ordenamientos/Bubble-sort/