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.
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.