Ordenamiento Burbuja

Material Didáctico Para el Lenguaje C

Creado Por: Sebastián LS / @sebastian9

Ordenamiento

El ordenamiento toma un arreglo desordenado A[ ] y lo convierte en uno ordenado.

Algoritmo para "Elevar la Burbuja"

  	arreglo[MAX]
  	índice <- 1
	límite_superior <- n - 1		

  	ciclo
  	  salir_si (índice > límite_superior)
  	  si (arreglo[índice] > arreglo[índice + 1]) entonces
  	    Intercambiar (arreglo[índice], arreglo[índice + 1])
  	  fin
  	  índice <- índice + 1
  	fin

					

La función Intercambiar

  funcion Intercambiar (a, b)
	  temporal <- a
	  a <- b
	  b <- temporal

					

Debes darte cuenta de que...

• En el ejemplo sólo el valor más grande fue colocado correctamente
• Todos los demás elementos están desordenados
• Es necesario repetir el proceso

Entonces cuántas veces hay que
Elevar la Burbuja?

Si tenemos N elementos...

Y si cada vez Elevamos uno de ellos a su posición correcta...

Tendremos que Elevar la Burbuja N - 1 veces para garantizar que hemos acomodado los elementos correctamente.

Elevamos

N - 1 veces

Optimicemos el número de comparaciones

En Azul se pueden ver el número de elementos
desordenados que quedan después de cada ciclo

En una elevación N, únicamente necesitamos hacer MAX - N comparaciones, por ejemplo:

• Es la tercera elevación
• Max es 5, el límite superior inicial
• Por lo tanto tenemos 2 comparaciones por hacer

¿Cómo se ve ahora?

  límite_superior <- n - 1

  ciclo
    salir_si (límite_superior = 0)
    índice <- 1
    ciclo
      salir_si (índice > límite_superior)
      si (arreglo[índice] > arreglo[índice + 1]) entonces
        Intercambiar (arreglo[índice], arreglo[índice + 1])
      fin
      índice <- índice + 1
    fin
    límite_superior <- límite_superior - 1
  fin

					

Agregamos un ciclo para reducir el límite superior
cada vez que se ordena un valor

Pero...

¿Y si tenemos un arreglo como este?

El programa ejecutará el procedimiento N-1 veces...
aunque sólo haya un elemento fuera de lugar.

Bandera Booleana

Para corregir el error hay que detectar la situación y salir antes del procedimiento

• Podemos usar una variable booleana para detectar si ocurrió algún intercambio en el procedimiento
• Si no ocurriera ningún intercambio sabremos que el arreglo ya está ordenado
• El valor de la variable deberá ser reiniciado cada vez que se ordene un número

Actualizamos nuestro Algoritmo

  cambio <- Verdadero  // Declaramos y asignamos valor a la variable
  límite_superior <- n - 1

  ciclo
	  salir_si ((límite_superior = 0) O (cambio = Falso)) // Aplicamos la condición
	  cambio <- Falso // Y reiniciamos la Variable
	  índice <- 1
	  ciclo
  		  salir_si (índice > límite_superior)
  		  si (arreglo[índice] > arreglo[índice + 1]) entonces
    		  Intercambiar (arreglo[índice], arreglo[índice + 1])    
    		  cambio = Verdadero // Confirmamos un cambio
  		  fin
  		  índice <- índice + 1
	  fin
	  límite_superior <- límite_superior - 1
  fin					
	  				

Ahora Pasemos todo a C

Elevar la Burbuja

						
for (i = 0; i < limite; i++) {
	if (arreglo[i] > arreglo [i+1]){
		intercambiar (&arreglo[i], &arreglo[i+1]);
		cambio = 1;
	}
}

					

La Función Intercambiar

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

  					

El Algoritmo con el Límite Disminuyendo

for (limite -= 1; !(limite == 0); limite--) {
	for (i = 0; i < limite; i++) {
		if (arreglo[i] > arreglo [i+1]){
			intercambiar (&arreglo[i], &arreglo[i+1]);
		}
	}
}
					

Comnezamos con N - 1, disminuimos N en cada iteración, y terminamos cuando ya no hay más comparaciones por hacer.

Bandera Booleana

char cambio = 1; // Declaramos la variable booleana
for (limite -= 1; (!(limite == 0) && cambio); limite--) { // Nueva condición
	cambio = 0; // Reiniciamos la variable
	for (i = 0; i < limite; i++) {
		if (arreglo[i] > arreglo [i+1]){
			intercambiar (&arreglo[i], &arreglo[i+1]);
			cambio = 1; // Confirmamos un cambio
		}
	}
}
					

Todo junto con últimos detalles

void intercambiar (int *a, int *b);

int main () {

	int limite, i, temp; // Temp remplaza a limite en el output
	int cambio = 1;
	int count = 0; // Verifica que el número de iteraciones sea el mínimo

	printf("Ingrese el número de elementos\n");
	scanf("%d", &limite);

	int arreglo[limite];

	printf("Ingrese %d elementos\n", limite);
	for (i = 0; i < limite; i++)
		scanf("%d", &arreglo[i]);

	temp = limite;

	for (limite -= 1; (!(limite == 0) && cambio); limite--) {
		cambio = 0;
		for (i = 0; i < limite; i++) {
			if (arreglo[i] > arreglo [i+1]){
				intercambiar (&arreglo[i], &arreglo[i+1]);
				cambio = 1;
			}
		}
		count++;
	}

	printf("Estos son los elementos ordenados:\n");
	for (i = 0; i < temp; i++)
		printf("%d\n", arreglo[i]);

	printf("Número de ciclos: %d\n", count);
}

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

¡Felicidades!
Ya sabes ordenamiento burbuja.