Algoritmo de la burbuja en Java (Bubble sort)

El algoritmo de la burbuja es un algoritmo de ordenamiento de arreglos popular, este dividirá el arreglo en 2 secciones o particiones, una ordenada y la otra desordenada, durante la ejecución la partición ordenada irá creciendo y la des ordenada irá disminuyendo.

A continuación se muestra un arreglo desordenado:

El algoritmo seguirá los siguientes pasos:

Se tomará el primer elemento y se comparará con el siguiente
En caso de que sea mayor se intercambiarán los elementos de posición
En caso de que sea menor se hará nada
del lado derecho se irá creando la partición ordenada

Veamos el código

Una vez que entendimos el algoritmo veamos como se ve el código:

public class BubbleSort {
	public void sortArray(int[] array) {
		for (int i = array.length - 1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if (array[j] > array[j + 1]) {
					swap(array, j, j+1);
				}
				printArray(array);
			}
			System.out.println("Change of partition index");
		}
	}

	public void printArray(int[] array) {
		for (int i = 0; i < array.length; i++) {
			System.out.printf("%d \t", array[i]);
		}
		System.out.println();
	}

	public void swap(int[] array, int a, int b) {
		int value = array[b];
		array[b] = array[a];
		array[a] = value;
	}

	public static void main(String[] args) {
		BubbleSort bubbleSort = new BubbleSort();
		int[] array = { 10, 1, 5, 40, 12, 34, 44, 12, 11, 9 };
		bubbleSort.printArray(array);
		bubbleSort.sortArray(array);
		bubbleSort.printArray(array);
	}
}

Ejecutando el algoritmo y analizando los resultados:

Una vez que ejecutamos la aplicación veremos la siguiente salida:

10 	1 	5 	40 	12 	34 	44 	12 	11 	9 	
1 	10 	5 	40 	12 	34 	44 	12 	11 	9 	
1 	5 	10 	40 	12 	34 	44 	12 	11 	9 	
1 	5 	10 	40 	12 	34 	44 	12 	11 	9 	
1 	5 	10 	12 	40 	34 	44 	12 	11 	9 	
1 	5 	10 	12 	34 	40 	44 	12 	11 	9 	
1 	5 	10 	12 	34 	40 	44 	12 	11 	9 	
1 	5 	10 	12 	34 	40 	12 	44 	11 	9 	
1 	5 	10 	12 	34 	40 	12 	11 	44 	9 	
1 	5 	10 	12 	34 	40 	12 	11 	9 	44 	
Change of partition index
1 	5 	10 	12 	34 	40 	12 	11 	9 	44 	
1 	5 	10 	12 	34 	40 	12 	11 	9 	44 	
1 	5 	10 	12 	34 	40 	12 	11 	9 	44 	
1 	5 	10 	12 	34 	40 	12 	11 	9 	44 	
1 	5 	10 	12 	34 	40 	12 	11 	9 	44 	
1 	5 	10 	12 	34 	12 	40 	11 	9 	44 	
1 	5 	10 	12 	34 	12 	11 	40 	9 	44 	
1 	5 	10 	12 	34 	12 	11 	9 	40 	44 	
Change of partition index
1 	5 	10 	12 	34 	12 	11 	9 	40 	44 	
1 	5 	10 	12 	34 	12 	11 	9 	40 	44 	
1 	5 	10 	12 	34 	12 	11 	9 	40 	44 	
1 	5 	10 	12 	34 	12 	11 	9 	40 	44 	
1 	5 	10 	12 	12 	34 	11 	9 	40 	44 	
1 	5 	10 	12 	12 	11 	34 	9 	40 	44 	
1 	5 	10 	12 	12 	11 	9 	34 	40 	44 	
Change of partition index
1 	5 	10 	12 	12 	11 	9 	34 	40 	44 	
1 	5 	10 	12 	12 	11 	9 	34 	40 	44 	
1 	5 	10 	12 	12 	11 	9 	34 	40 	44 	
1 	5 	10 	12 	12 	11 	9 	34 	40 	44 	
1 	5 	10 	12 	11 	12 	9 	34 	40 	44 	
1 	5 	10 	12 	11 	9 	12 	34 	40 	44 	
Change of partition index
1 	5 	10 	12 	11 	9 	12 	34 	40 	44 	
1 	5 	10 	12 	11 	9 	12 	34 	40 	44 	
1 	5 	10 	12 	11 	9 	12 	34 	40 	44 	
1 	5 	10 	11 	12 	9 	12 	34 	40 	44 	
1 	5 	10 	11 	9 	12 	12 	34 	40 	44 	
Change of partition index
1 	5 	10 	11 	9 	12 	12 	34 	40 	44 	
1 	5 	10 	11 	9 	12 	12 	34 	40 	44 	
1 	5 	10 	11 	9 	12 	12 	34 	40 	44 	
1 	5 	10 	9 	11 	12 	12 	34 	40 	44 	
Change of partition index
1 	5 	10 	9 	11 	12 	12 	34 	40 	44 	
1 	5 	10 	9 	11 	12 	12 	34 	40 	44 	
1 	5 	9 	10 	11 	12 	12 	34 	40 	44 	
Change of partition index
1 	5 	9 	10 	11 	12 	12 	34 	40 	44 	
1 	5 	9 	10 	11 	12 	12 	34 	40 	44 	
Change of partition index
1 	5 	9 	10 	11 	12 	12 	34 	40 	44 	
Change of partition index
1 	5 	9 	10 	11 	12 	12 	34 	40 	44

En la salida anterior podemos analizar el siguiente comportamiento:

Los elementos se van cambiando de izquierda a derecha
La partición ordenada se encontrará del lado derecho e irá creciendo cada que veamos el log «Change of partition index»
La partición desordenada se encontrará del lado izquierdo e irá decreciendo cada que veamos el log «Change of partition index»
Es posible que antes de que termine el algoritmo el arreglo ya se encuentre ordenado, pero tiene que terminar la ejecución para asegurarlo

Características del algoritmo

No requiere de arreglos adicionales para realizar el ordenamiento
La complejidad es de O(n²)
El performance se reduce cuando crece el número de elementos en el arreglo

Para estar al pendiente sobre nuestro contenido nuevo síguenos en nuestras redes sociales https://www.facebook.com/devs4j/ y https://twitter.com/devs4j.

Si hay algún algoritmo que te gustaría que desarrollemos coméntenlo en nuestras redes sociales o en la sección de comentarios del post.