Bubble sort (Burbuja)
El método de ordenamiento burbuja es un algoritmo de ordenamiento sencillo pero ineficiente para grandes conjuntos de datos. Aquí tienes más detalles sobre su funcionamiento y características:
Funcionamiento
- Comparación de elementos adyacentes: Compara cada par de elementos adyacentes en el arreglo.
- Intercambio: Si un elemento es mayor que el siguiente, se intercambian.
- Repetición: Este proceso se repite para cada elemento del arreglo hasta que no se necesiten más intercambios, lo que indica que el arreglo está ordenado.
Características
- Simplicidad: Es fácil de entender e implementar.
- Complejidad: Tiene una complejidad temporal de O(n2)
- en el peor y promedio de los casos, donde n
- es el número de elementos en el arreglo.
- Eficiencia: No es eficiente para grandes conjuntos de datos debido a su alta complejidad temporal.
- Estabilidad: Es un algoritmo estable, lo que significa que no cambia el orden relativo de los elementos con valores iguales.
Ejemplo en lenguaje C
#include <stdio.h>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// Últimos i elementos ya están en su lugar
for (int j = 0; j < n - i - 1; j++) {
// Intercambiar si el elemento actual es mayor que el siguiente
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void printArray(int arr[], int size) {
for (int 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: ");
printArray(arr, n);
return 0;
}
Ventajas:
- Fácil implementación.
- No requiere memoria adicional.
- Realiza pocos intercambios.
- Rendimiento constante: poca diferencia entre el peor y el mejor caso.
Desventajas:
- Lento.
- Realiza numerosas comparaciones.
Este es un algoritmo lento. No obstante, ya que sólo realiza un intercambio en cada ejecución del ciclo externo, puede ser una buena opción para listas con registros grandes y claves pequeñas. Si miras el programa de demostración notarás que es el más rápido en la parte gráfica (por lo menos en un PC lento y con una tarjeta gráfica mala como el mío x-|). La razón es que es mucho más lento dibujar las barras que comparar sus largos (el desplazamiento es más costoso que la comparación), por lo que en este caso especial puede vencer a algoritmos como Quicksort