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.

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com