Ordenación Shell (por peine) - Algoritmos de ordenación (2/6)
Hoy vamos a seguir con nuestra serie de algoritmos de ordenación. Después de la ordenación por burbuja, hoy le toca el turno a la ordenación Shell.
Go!
Es una variación de la ordenación por burbuja. Si recordamos la ordenación por burbuja, consistía en tomar un par de elementos adyacentes y reordenarlos. Después tomar el par anterior y repetir. Cuando lleguemos al principio, repetimos el proceso completo hasta terminar de ordenar.
Bien, ¿qué ocurre si en lugar de tomar dos elementos adyacentes, tomamos un par de elementos separados una distancia X?
Supongamos el mismo array desordenado de la otra vez. Y comenzaremos tomando la distancia máxima, es decir, el primero y último:
VUELTA 1 2 - 5 - 6 - 8 - 9 - 3 - 7 - 6 - 1 - 0 ^ ^
Como están colocados al revés, reordenamos
0 - 5 - 6 - 8 - 9 - 3 - 7 - 6 - 1 - 2
Ahora, tomamos una distancia más pequeña y vamos retrocediendo como en burbuja.
VUELTA 2 0 - 5 - 6 - 8 - 9 - 3 - 7 - 6 - 1 - 2 ^ ^ 0 - 5 - 6 - 2 - 9 - 3 - 7 - 6 - 1 - 8 ^ ^ 0 - 5 - 1 - 2 - 9 - 3 - 7 - 6 - 6 - 8 ^ ^ 0 - 5 - 1 - 2 - 9 - 3 - 7 - 6 - 6 - 8 ^ ^ 0 - 5 - 1 - 2 - 9 - 3 - 7 - 6 - 6 - 8
Ahora, reducimos aún más la distancia
VUELTA 3 0 - 5 - 1 - 2 - 9 - 3 - 7 - 6 - 6 - 8 ^ ^ 0 - 5 - 1 - 2 - 9 - 3 - 7 - 6 - 6 - 8 ^ ^ 0 - 5 - 1 - 2 - 6 - 3 - 7 - 6 - 9 - 8 ^ ^ 0 - 5 - 1 - 2 - 6 - 3 - 7 - 6 - 9 - 8 ^ ^ 0 - 5 - 1 - 2 - 6 - 3 - 7 - 6 - 9 - 8 ^ ^ 0 - 3 - 1 - 2 - 6 - 5 - 7 - 6 - 9 - 8 ^ ^ 0 - 3 - 1 - 2 - 6 - 5 - 7 - 6 - 9 - 8
Y así sucesivamente.
Procedemos a implementar
Necesitamos, como en burbuja, una variable que nos lleve la cuenta de las inversiones que hacemos en una vuelta.
int swaps = 0;
Y otra variable que nos lleve la cuenta del “hueco” o “distancia” entre elementos a comparar. Dicha distancia comienza desde el máximo (longitud del array menos 1)
int gap = arr.length-1;
Llegamos al bucle.
while(swaps>0 || gap>1) { swaps=0;
En este caso, nuestra j va desde el final, hasta lo mínimo posible, es decir, hasta que el elemento a comparar (a la izquierda, separado gap unidades) sea el primero.
for (int j=this.arr.length-1; j-gap>=0; j--) { //j=0
Comprobamos si tenemos que invertir
if (this.arr[j] < this.arr[j-gap]) { int aux = this.arr[j]; this.arr[j] = this.arr[j-gap]; this.arr[j-gap] = aux; swaps++; }
Una vez hemos hecho la vuelta completa, tenemos que reducir el gap. La reducción se hace dividiendo la distancia entre 1.3, que se ha estudiado que es un buen coeficiente.
if (gap>1) { gap = (int) (gap / 1.3); }
Además, se ha demostrado que si cuando el hueco debería ser 9 o 10, se configura como 11, el algoritmo mejora.
if (gap==9 || gap==10) { gap = 11; } }
Como veis el algoritmo es similar a la ordenación por burbuja pero este es mucho más eficiente.
Aquí está el código del archivo CombSort.java y el del repositorio completo hasta la fecha de hoy
Podéis encontrar todos los posts sobre Algoritmos de ordenación en el tag #SortingAlgorithms