Ordenamiento Shell
Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso.
El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones: El Algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones.
Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada.
Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños.
El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.
Considere un valor pequeño que está inicialmente almacenado en el final del vector que se quiere ordenar de forma ascendente.
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 solo unas pocas comparaciones e intercambios.
Repita este proceso, cada vez con un número menor de columnas más largas.
Mientras que transformar la lista en una tabla hace más fácil visualizarlo, el algoritmo propiamente hace su ordenamiento en contexto (incrementando el índice por el tamaño de paso, esto es usando i += tamaño_de_paso en vez de i++).
Algunos libros de texto y referencias antiguas le llaman ordenación "Shell-Metzner" por Marlene Metzner Norton, pero según Metzner, "No tengo nada que ver con el algoritmo de ordenamiento, y mi nombre nunca debe adjuntarse a éste."
[1] La secuencia de espacios es una parte integral del algoritmo Shell sort.
Cualquier secuencia incremental funcionaría siempre que el último elemento sea 1.
La secuencia de espacios que fue originalmente sugerida por Donald Shell debía comenzar con
Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos cuadráticos como el ordenamiento por inserción, se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso.
del peor caso, si los datos están inicialmente en el vector como (pequeño_1, grande_1, pequeño_2, grande_2, ...) - es decir, la mitad alta de los números están situados, de forma ordenada, en las posiciones con índice par y la mitad baja de los números están situados de la misma manera en las posiciones con índice 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 está ordenado en caso de considerarlo aislado.
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.
(usando los incrementos de Shell que comienzan con n/2, n el tamaño del vector y se dividen por 2 cada vez),
, y posiblemente mejores tiempos de ejecución no comprobados.
en el peor caso del Shell sort permanece como una pregunta por resolver.
