Burbuja

El término algoritmo de Burbuja, “Bubble Sort”, fue utilizado por primera vez por Kenneth E. Iverson en 1.962, pero al algoritmo ya se le conocía anteriormente con el nombre de “Clasificación por intercambio” debido a un trabajo de Edward H. Friend en 1.954. Este algoritmo no es práctico cuando el nº de elementos (n) es grande, dado que su complejidad en el peor de los casos es О (n2). En determinadas circunstancias e introduciendo una pequeña modificación en el código, se prodría llegar a tener (n) en el mejor de los casos, no perder el tiempo en ello.

 

Kenneth E. Iverson. Buble sort.

Rendimiento – Complejidad
Mejor caso Ω
Peor caso O
Media Θ
Espacio
(n) (n 2) (n 2) O(1)

 

Es el método más “básico” de ordenación, trabaja de la siguiente forma:

Tomamos el primer elemento del vector y lo comparamos con los demás, si encontramos un elemento menor que él, intercambiamos sus valores y volvemos a repetir el proceso desde la posición inicial del vector hasta que cada elemento tenga la posición correcta.

 

 

Ejemplo.

El algoritmo básico programado en Java.

 

public static int[] burbuja(int[] Vectort) {
    boolean clasificado = false;
    int intercambio;
    while (!clasificado) {
      clasificado = true;
      for (int i = 0; i < Vectort.length - 1; i++) {
        if (Vectort[i] > Vectort[i + 1]) {
          intercambio = Vectort[i];
          Vectort[i] = Vectort[i + 1];
          Vectort[i + 1] = intercambio;
          clasificado = false;
        }
      }
    }
    return Vectort;
  }

 

 

Algoritmo mejorado.

public static int[] Ordenanburbuja1(int[] Vectorb) {
    int longitudV = Vectorb.length;
    int intercambio;
    for (int i = 0; i < longitudV; i++) {
      for (int j = i + 1; j < longitudV; j++) {
        if (Vectorb[i] > Vectorb[j]) {
          intercambio = Vectorb[i];
          Vectorb[i] = Vectorb[j];
          Vectorb[j] = intercambio;
        }
      }
    }
    return Vectorb;
  }

Rendimiento.

Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación. El rendimiento del Burbuja 1 (mejorado) es superior al de Burbuja básico. Hasta la ordenación de 1.000 elementos las diferencias son pequeñas, posteriormente Burbuja 1 es mejor salvo en la ordenación ascendente.

 

? Pulsar  sobre los gráficos para verlos a tamaño real.

 

Rendimiento algoritmo de burbuja de 10 a 100mil elementosRendimiento algoritmo de burbuja de 100mil a 1Millón de elementos

 

Rendimiento algoritmo de burbuja1 de 10 a 100 mil elementosRendimiento algoritmo de burbuja1 de 100mil a 1Millón de elementos

 

 

Diferencia de rendimiento entre las dos versiones del algoritmo de Burbuja