Método Burbuja Mejorado

Como ya sabemos mediante el método burbuja, dado un arreglo de n números, se requiere de n-1 pasos para dejar el arreglo ordenado.

Se puede observar que en el primer paso el primer elemento mayor queda en la primera posición mayor (última si es que estamos ordenando de menor a mayor); en el segundo paso el segundo elemento mayor queda en la segunda posición mayor (penúltima); y así sucesivamente. Por esta razón el número de comparaciones, debería irse reduciendo en uno, en cada paso.

Se puede observar además, que en muchos caso se consigue tener ordenado el arreglo, en un número menor de pasos a n-1, por lo cual el resto de los pasos serían innecesarios.

Considerando estos dos hechos se podría mejorar el método burbuja eliminando los pasos innecesarios y reduciendo las comparaciones con cada paso.

Una manera sencilla de hacer esto sería detectando mediante algún registro si se han efectuado cambios o no, y reduciendo el número de comparaciones en cada paso.

A continuación se muestra un fragmento de código que permite realizar estas mejoras:

float X[100], AUX;
int N, paso, j;
int bandera=1;
.
.
.
for(paso=0;paso<N-1&&bandera==1;paso++)
/* si en el paso anterior no hubo cambios se detiene ciclo */
  {
	bandera=0;
	for(j=0;j<N-paso-1;j++)
	/* las comparaciones van dismuyendo
	a medida que se efectuan los pasos */
	  {
		if(X[j]<X[j+1])
		  {
			bandera=1; /* indica si se han realizados cambios o no */
			AUX=X[j];
			X[j]=X[j+1];
			X[j+1]=AUX;
		  }
	  }
  }

Ejemplo Código Método Burbuja burbuja2.zip