3 - Bubble Sort

Bubble Sort es el algoritmo de ordenamiento más conocido y uno de los más sencillos de implementar en C. Su mecánica se basa en recorrer el array varias veces, comparando pares adyacentes y haciendo que el elemento más grande “burbujee” hacia el final en cada pasada.

3.1 Idea general del algoritmo

El algoritmo realiza pasadas sucesivas sobre la lista. En cada pasada, examina cada par adyacente y los intercambia si están fuera de orden. Al finalizar la primera pasada, el elemento más grande queda al final; en la segunda, el segundo más grande queda en la penúltima posición, y así sucesivamente.

3.2 Comparación de elementos adyacentes

El recorrido interno compara arr[j] con arr[j + 1]. Si el orden deseado es ascendente y arr[j] > arr[j + 1], se produce un intercambio.

3.3 Intercambio (swap) cuando es necesario

El intercambio se realiza con la función swap definida previamente:

void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

Centralizar esta operación evita duplicar código y reduce errores.

3.4 Burbujeo del mayor al final

Cada pasada garantiza que el mayor de la porción revisada termina al final de la sección considerada. Por eso el límite interno puede reducirse en cada iteración externa: no es necesario volver a tocar las posiciones ya ordenadas al final del array.

3.5 Optimización: cortar si no hubo swaps

Si en una pasada completa no se realiza ningún intercambio, la lista ya está ordenada y el algoritmo puede detenerse. Esto mejora mucho el rendimiento en listas casi ordenadas.

3.6 Implementación paso a paso en C

Versión clásica con corte temprano; se asume que swap ya está declarada.

void bubble_sort(int *arr, int n) {
  for (int i = 0; i < n - 1; i++) {
    int hubo_intercambio = 0;
    int limite = n - 1 - i; /* el último ya quedó en su lugar */
    for (int j = 0; j < limite; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(&arr[j], &arr[j + 1]);
        hubo_intercambio = 1;
      }
    }
    if (!hubo_intercambio) {
      break; /* la lista ya está ordenada */
    }
  }
}

Explicación línea por línea:

• for (int i = 0; i < n - 1; i++): controla las pasadas; tras cada pasada, el mayor de la sección queda al final.
• int hubo_intercambio = 0;: flag para saber si en esta pasada hubo cambios.
• int limite = n - 1 - i;: evita comparar posiciones finales ya ordenadas.
• for (int j = 0; j < limite; j++): recorre pares adyacentes dentro del rango vigente.
• if (arr[j] > arr[j + 1]): detecta si el par está desordenado para el orden ascendente.
• swap(&arr[j], &arr[j + 1]);: intercambia los elementos fuera de orden.
• hubo_intercambio = 1;: marca que hubo al menos un swap en esta pasada.
• if (!hubo_intercambio) break;: si no hubo swaps, la lista ya estaba ordenada y se corta el algoritmo.

3.7 Complejidad temporal y espacial

• Tiempo: O(n^2) en promedio y peor caso (listas inversas); O(n) en el mejor caso si el corte temprano detecta una lista ya ordenada.
• Memoria: O(1) espacio adicional; trabaja in-place.
• Estabilidad: es estable, no cambia el orden relativo de elementos iguales.

3.8 Ventajas y desventajas

• Ventajas: implementación muy simple; estable; fácil de depurar paso a paso; buen rendimiento si la lista ya está casi ordenada gracias al corte temprano.
• Desventajas: rendimiento pobre en listas medianas o grandes; su complejidad cuadrática lo hace inviable para grandes volúmenes de datos.

3.9 Casos ideales y peores casos

• Ideal: listas pequeñas o casi ordenadas donde el corte temprano termina rápido.
• Peor caso: lista ordenada en sentido inverso; requiere la máxima cantidad de comparaciones e intercambios.

Bubble Sort sigue siendo valioso para docencia y para validar otros algoritmos: su simplicidad permite comparar resultados y detectar errores en implementaciones más complejas.

3.10 Archivos para un proyecto en CLion

Para practicar Bubble Sort en un proyecto limpio de CLion, incluye estos archivos:

• swap.h y swap.c: declaración e implementación de la función de intercambio.
• utils.h y utils.c: funciones de impresión y utilidades compartidas.
• bubble_sort.c: implementación del algoritmo con su prototipo.
• main.c: carga arrays de prueba, invoca bubble_sort y muestra el antes y después.

Con esta estructura modular puedes compilar rápido, hacer step-by-step y reutilizar los mismos helpers en los otros algoritmos del tutorial. Códigos completos:

/* swap.h */
void swap(int *a, int *b);

/* swap.c */
#include "swap.h"

void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

/* utils.h */
void imprimir_array(const int *arr, int n);

/* utils.c */
#include <stdio.h>
#include "utils.h"

void imprimir_array(const int *arr, int n) {
  printf("[");
  for (int i = 0; i < n; i++) {
    printf("%d", arr[i]);
    if (i + 1 < n) {
      printf(", ");
    }
  }
  printf("]\n");
}

/* bubble_sort.c */
#include "swap.h"

void bubble_sort(int *arr, int n) {
  for (int i = 0; i < n - 1; i++) {
    int hubo_intercambio = 0;
    int limite = n - 1 - i;
    for (int j = 0; j < limite; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(&arr[j], &arr[j + 1]);
        hubo_intercambio = 1;
      }
    }
    if (!hubo_intercambio) {
      break;
    }
  }
}

/* main.c */
#include <stdio.h>
#include "swap.h"
#include "utils.h"

void bubble_sort(int *arr, int n); /* prototipo */

int main(void) {
  int datos[] = {5, 2, 9, 1, 3};
  int n = sizeof(datos) / sizeof(datos[0]);

  printf("Antes: ");
  imprimir_array(datos, n);

  bubble_sort(datos, n);

  printf("Despues: ");
  imprimir_array(datos, n);
  return 0;
}