¿Qué es la ordenación por burbuja?
La ordenación por burbuja es un algoritmo de ordenamiento simple que funciona comparando elementos adyacentes de una lista y, si están en el orden incorrecto, los intercambia. Imagina una columna de burbujas en un líquido: las más grandes «burbujean» hacia arriba hasta alcanzar su posición correcta. De ahí su nombre.
Origen e historia
Aunque no se conoce un inventor específico, el algoritmo de ordenación por burbuja es uno de los primeros algoritmos de ordenamiento enseñados en la introducción a la programación. Su simplicidad lo hace ideal para enseñar los conceptos básicos de algoritmos y estructuras de datos.
¿Cómo funciona?
Comparación de elementos adyacentes: Se comparan los elementos de la lista de dos en dos.
Intercambio si están desordenados: Si el primer elemento es mayor que el segundo, se intercambian.
Repeticiones: Este proceso se repite varias veces hasta que la lista esté completamente ordenada.
Código en C y explicación
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Intercambio de elementos
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Función para imprimir el arreglo
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Arreglo ordenado en orden ascendente: \n");
printArray(arr, n);
return 0;
}Explicación línea por línea:
1. Inclusión de la biblioteca: #include <stdio.h> para entrada y salida estándar.
2. Función bubbleSort:
Parámetros: arr (arreglo a ordenar), n (tamaño del arreglo).
Bucles anidados:
– El bucle externo (i) controla el número de pasadas.
– El bucle interno (j) compara elementos adyacentes en cada pasada.
– Condición de intercambio: Si el elemento actual es mayor que el siguiente, se intercambian.
3. Función printArray: Imprime los elementos del arreglo.
4. Función main:
– Arreglo de ejemplo: Se define un arreglo de números enteros.
– Llamada a bubbleSort: Se ordena el arreglo.
– Impresión del resultado: Se imprime el arreglo ordenado.
¿Por qué usar la ordenación por burbuja?
Simple de entender: Es fácil de visualizar y explicar.
Implementación sencilla: El código es conciso y fácil de escribir.
Desventajas
Ineficiente para grandes conjuntos de datos: Tiene una complejidad temporal de O(n²), lo que significa que su tiempo de ejecución aumenta cuadráticamente con el tamaño de la entrada.
Muchos intercambios innecesarios: Realiza muchos intercambios, incluso cuando la lista ya está casi ordenada.
La ordenación por burbuja es un algoritmo útil para aprender los conceptos básicos de ordenamiento, pero no es la mejor opción para aplicaciones reales que requieran un alto rendimiento, especialmente con grandes conjuntos de datos.