Descripción
El algoritmo Shell es una mejora de la ordenación por inserción, donde se van
comparando elementos distantes, al tiempo que se los intercambian si
corresponde. A medida que se aumentan los pasos, el tamaño de los saltos
disminuye; por esto mismo, es útil tanto como si los datos desordenados se
encuentran cercanos, o lejanos.
Es bastante adecuado para ordenar listas de tamaño moderado, debido a que su
velocidad es aceptable y su codificación es bastante sencilla. Su velocidad
depende de la secuencia de valores con los cuales trabaja, ordenándolos.El
siguiente ejemplo muestra el proceso de forma gráfica:
Considerando un valor pequeño que está inicialmente almacenado en el final del
vector. Usando un ordenamiento O(n2) como el ordenamiento de burbuja o el
ordenamiento por inserción, tomará aproximadamente n comparaciones e
intercambios para mover este valor hacia el otro extremo del vector.
El Shell sort primero mueve los valores usando tamaños de espacio gigantes, de
manera que un valor pequeño se moverá bastantes posiciones hacia su
posición final, con sólo unas pocas comparaciones e intercambios.
Ejemplo
Por ejemplo, considere una lista de números como [13 14 94 33 82 25 59 94 65 23 45
27 73 25 39 10]. Si comenzamos con un tamaño de paso de 8, podríamos visualizar
esto dividiendo la lista de números en una tabla con 5 columnas. Esto quedaría así:
Entonces ordenamos cada columna, lo que nos queda:
Cuando lo leemos de nuevo como una única lista de números, obtenemos [ 10 14 73
25 23 13 27 94 33 39 25 59 94 65 82 45 ]. Aquí, el 10 que estaba en el extremo final,
se ha movido hasta el extremo inicial.
Esta lista es entonces de nuevo ordenada usando un ordenamiento con un espacio de
3 posiciones, y después un ordenamiento con un espacio de 1 posición (ordenamiento
por inserción simple).
Secuencia de espacios
La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier
secuencia incremental funcionaría siempre que el último elemento sea 1. El algoritmo
comienza realizando un ordenamiento por inserción con espacio, siendo el
espacio el primer número en la secuencia de espacios. Continua para realizar un
ordenamiento por inserción con espacio para cada número en la secuencia,
hasta que termina con un espacio de 1.
Cuando el espacio es 1, el ordenamiento por inserción con espacio es
simplemente un ordenamiento por inserción ordinario, garantizando que la lista
final estará ordenada. La secuencia de espacios que fue originalmente sugerida por
Donald Shell debía comenzar con N / 2 y dividir por la mitad el número hasta alcanzar
1.
Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre
los algoritmos cuadráticos como el ordenamiento por insercióse puede cambiar
ligeramente para disminuir más el tiempo necesario medio y el del peor ca n, so.
Quizás la propiedad más crucial del Shell sort es que los elementos permanecen
k-ordenados incluso mientras el espacio disminuye.
Se dice que un vector dividido en k subvectores esta k-ordenado si cada uno de esos
subvectores esta ordenado en caso de considerarlo aislado. Por ejemplo, si una lista
fue 5-ordenada y después 3-ordenada, la lista está ahora no sólo 3-ordenada,
sino tanto 5-ordenada como 3-ordenada. Si esto no fuera cierto, el algoritmo
desharía el trabajo que había hecho en iteraciones previas, y no conseguiría un
tiempo de ejecución tan bajo.
Análisis del Costo Computacional
Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es
muy difícil analizar su tiempo de ejecución. Dependiendo de la elección de la
secuencia de espacios, Shell sort tiene un tiempo de ejecución en el peor caso de
O(n2) (usando los incrementos de Shell que comienzan con 1/2 del tamaño del
vector y se dividen por 2 cada vez), O(n3 / 2) (usando los incrementos de
Hibbard de 2k − 1), O(n4 / 3) (usando los incrementos de Sedgewick de 9(4i) −
9(2i) + 1, o 4i + 1 + 3(2i) + 1), o O(nlog2n), y posiblemente mejores tiempos de
ejecución no comprobados. La existencia de una implementación O(nlogn) en el
peor caso del Shell sort permanece como una pregunta por resolver.
Implementación
A continuación se muestra el Ordenamiento Shell en algunos de los lenguajes de
programación de alto nivel más usados:
C
