Diferencia entre revisiones de «Ordenamiento Shell»

La secuencia de espacios que fue originalmente sugerida por [[Donald Shell]] debía comenzar con <math>N/2</math> 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ón]], se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia permite un ordenamiento <math>O(n^2)</math> 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 impar.

 

 

Dependiendo de la elección de la secuencia de espacios, Shell sort tiene un tiempo de ejecución en el peor caso de <math>O(n^2)</math> (usando los incrementos de Shell que comienzan con n/2, n el tamaño del vector y se dividen por 2 cada vez), <math>O(n^{3/2})</math> (usando los incrementos de Hibbard de <math>2^k -1</math>), <math>O(n^{4/3})</math> (usando los incrementos de Sedgewick <math>O(n\log^2 n)</math>, y posiblemente mejores tiempos de ejecución no comprobados. La existencia de una implementación <math>O(n \log n)</math> en el peor caso del Shell sort permanece como una pregunta por resolver.