Burbuja es uno de los algoritmos de ordenamiento más sencillos y es un buen ejercicio de práctica para introducir este tipo de algoritmos. A pesar de su simple implementación, los usos que se le puede dar son muchos y muy útiles en aplicaciones de la vida real.
Los algoritmos de ordenamiento son de gran utilidad para la clasificación de elementos, sea de forma ascendente o descendente, para ejecutar distintas operaciones sobre ellos ya estando ordenados: búsqueda de elementos, determinar el elemento más grande, el par más cercano, unicidad de elementos, entre otros.
La idea principal del algoritmo burbuja es comparar los elementos de forma adyacente. Si el primer elemento es menor al segundo elemento, está en orden. De lo contrario, estos dos se intercambian de forma que queden ordenados. Luego, compara el segundo elemento con el tercero y realiza las mismas operaciones: no hay cambio si el segundo elemento es menor al tercero; hay cambio si el segundo elemento es mayor al tercero. De esta forma, se va reestructurando el arreglo de forma ascendente.
Finalmente, el algoritmo necesita saber cuando detenerse, y por esto, se usa una bandera llamada generalmente “swapped” o “cambio”. Al inicio de cada iteración está en false y si durante las iteraciones sucede un cambio, la bandera se cambia a true. El momento en que en una iteración no se realizó ningún cambio y al estar la bandera en false, indica que el arreglo está ordenado y termina el procedimiento.
Otro punto a tener en cuenta es que, al final de cada iteración, los valores más altos ya están al final del arreglo. Por lo tanto, la próxima iteración no necesita tomar en cuenta estos últimos valores.
Una representación gráfica para entender mejor el procedimiento:
Implementado en código en C++
void bubbleSort(int arr[], int n) { |
Importante que, en el segundo for, se recorre el arreglo hasta n - i - 1, indicando que no se toma en cuenta los últimos elementos ya que estos están ordenados y no es necesario que sean evaluados. También, entiéndase por la función “swap” como una que intercambia los valores que recibe como parámetro.
El algoritmo de ordenamiento burbuja es una de las implementaciones más sencillas y puede ser aprovechada para muchos proyectos, pequeños o grandes, que requieran del ordenamiento de datos para su consulta, búsqueda u operar sobre ellos de la manera en que requiera.
Referencias
Joyanes Aguilar, L., & Zahonero Martínez, I. (1998). Estructura de Datos algoritmos, abstracción y objetos. (1.a ed.). New York, Estados Unidos: McGraw-Hill Education.
GeeksforGeeks. (2020, 30 septiembre). Bubble Sort. Recuperado 20 de noviembre de 2020, de https://www.geeksforgeeks.org/bubble-sort/
tutorialspoint. (s. f.). Data Structure - Bubble Sort Algorithm - Tutorialspoint. Recuperado 20 de noviembre de 2020, de https://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm
QUORA. (s. f.). What are the uses of different sorting algorithms like bubble, selection, insertion, shell, merge, heap, quick, tree, radix, counting and bucket sort in real-life scenarios? Recuperado 20 de noviembre de 2020, de https://www.quora.com/What-are-the-uses-of-different-sorting-algorithms-like-bubble-selection-insertion-shell-merge-heap-quick-tree-radix-counting-and-bucket-sort-in-real-life-scenarios