METODO DE BURBUJA MEJORADO Y DE INSERCION

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;

}

}

}

INSERCION DIRECTA

Este método ordena el vector desplazando los elementos mayores hacia la parte derecha y los inferiores hacia la izquierda

La sub que ordena el array, se le debe enviar como parámetro la matriz a ordenar y en el segundo parámetro el modo de ordenación , es decir en forma Ascendente o Descendente.

Nota: para optimizar la velocidad de ordenación, sobre todo si son muchos elementos,

...