Algoritmo de ordenación de Burbuja bidireccional (ordenación por sacudida o Cocktail Sort)

Artículo perteneciente a la sección de algoritmos

Este artículo es una evolución del algoritmo de ordenación por burbuja

Hola a todos,

Si ya habéis visto como funciona el algoritmo de ordenación por burbuja habréis observado que es fácil llevar los números grandes hasta el final de la lista, pero que es complicado llevar los números pequeños al inicio de la lista. Dependiendo de como estén ordenados los números a priori se puede llegar a tardar bastante en ordenarlos.

La solución es sencilla... ordenar con el método de burbuja y cuando llegamos al final de la primera iteración, no volver a realizar el cálculo desde el principio sino que empezaremos desde el final hasta al inicio. De esta manera siempre se consigue que tanto los números pequeños como los números grandes se desplacen a los extremos de la lista lo más rápido posible. Esto otorga el beneficio adicional que la lista cada vez se nos hace más pequeña (en los extremos de la lista vamos almacenando los elementos defnifitivos que nunca más se tendrán que mirar).

El código es tal que así (solo tiene fines educativos, no es una implementación terriblemente eficiente):

void LPVector::CocktailSort(void)
{
int i , j = 0 ;
float temp = 0.0;

do
{
for (i = j ; i < (n-1-j); ++i)
{
if(v[i] > v[i+1])
{
temp = v[i+1];
v[i+1] = v[i];
v[i] = temp;
}
}

if(!this->IsSorted())
{
for (i = ( n - 1 - j ) ; i > j ; --i)
{
if(v[i] < v[i-1])
{
temp = v[i-1];
v[i-1] = v[i];
v[i] = temp;
}
}
}

j++;

}while(!this->IsSorted());
}

Espero que esta idea tan sencilla para mejorar el algoritmo de burbuja os inspire para buscarle más soluciones a vuestros problemas.

Nos vemos