shellsorf

El método de ordenación shellsort es una versión mejorada del método de ordenación por inserción directa, que se utiliza cuando el número de elementos es grande. Este método recibe su nombre graciasa su creados Donald L. Shell, también se conoce con el nombre inserción con incrementos decrecientes.

En el método de ordenación por inserción directa, cada elemento se compara con los elementoscontiguos de su izquierda de uno por uno, para lograr su ordenamiento; si por ejemplo, el elemento a comparar es el más pequeño y se encuentra en la última posición del arreglo, hay que ejecutar muchascomparaciones antes de colocar el elemento en su lugar de forma definitiva.

El método de ordenación shellsort mejora el ordenamiento por inserción comparando elementos separados por un espacio devarias posiciones. Esto permite que un elemento haga pasos más grandes hacia la posición que debe ocupar. Los pasos múltiples sobre los elementos se hacen con tamaños de espacio cada vez más pequeñosy el último paso del método es un simple ordenamiento por inserción directa, pero para entonces, los elementos de arreglo ya casi están ordenados.

Para determinar el tamaño de los incrementos(saltos) constantes, el primero debe ser generado a partir del tamaño del arreglo entre dos, obteniendo solo su parte entera de la división o redondeando el resultado de la misma, y posteriormente irreduciendo a la mitad el incremento en cada repetición, hasta que el incremento sea un uno.

El procedimiento para aplicar el algoritmo de shellsort es el siguiente:

Generar un ciclo que se encarguede controlar el tamaño que deben tener los incrementos.
Este ciclo debe iniciar con la división del tamaño del arreglo entre dos.
Mientras que el incremento sea mayor a cero debe continuar.
Y elcambio de incremento se elige de entre dos opciones: un uno o la división del incremento anterior entre dos.

Un segundo ciclo dentro del anterior, controla el número de comparaciones que se deben...