Trabajo de shellsort

Republica bolivariana de Venezuela
Ministerio del poder popular para la educación
Instituto universitario de mercadotecnia
Carrera: Informática




ShellSort




Índice

Introducción…………………………………………………………………………………..3
Origen del ShellSort…………………………………………………………………..…4, 5
Características……………………………………………………………………………....6
Descripción del algoritmo de ordenamientoShellSort…………………………… ….7, 8
Búsqueda binaria……………………………………………………………………….9, 10
Conclusión…………………………………………………………………………………..11
Bibliografía…………………………………………………………………………………..12












Introducción
El algoritmo de ordenación de Shell. Debe su nombre al ingeniero y matemático estadounidense Donald Shell , que lo publicó en la revista Communications of the ACM  en 1959.
Es un algoritmo de ordenación interna muysencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección directa o el de inserción directa.
Aunque a menudo, es un algoritmo un tanto olvidado por dos motivos: en primer lugar, en los cursos básicos de programación se suele pasar por alto o se pasa "de puntillas" por estealgoritmo, dado que su comprensión requiere un cierto esfuerzo y algo de tiempo, y se suele centrar la atención en los tres algoritmos más básicos (burbuja, selección e inserción); y en segundo lugar, el algoritmo QuickSort, desarrollado por Hoare en 1962 puede dar mejores resultados aún que éste, con lo cual, le suele hacer bastante sombra en los temarios de los cursos de programación básicos.Sin embargo, es necesario romper una lanza a favor del algoritmo ShellSort, ya que es el mejor algoritmo de ordenación in-situ... es decir, el mejor de aquellos en los que la cantidad de memoria adicional que necesita -aparte de los propios datos a ordenar, claro está- es constante, sea cual sea la cantidad de datos a ordenar. El algoritmo de la burbuja, el de selección directa, el de insercióndirecta y el de Shell son todos in-situ, y éste último, el de Shell, es el que mejor resultados da, sin ninguna duda de todos ellos y sus posibles variantes.
Por supuesto que otros métodos de ordenación, como QuickSort, BinSort, HeapSort o RadixSort pueden pueden superar a ShellSort en cuanto al tiempo de ejecución, pero ninguno de ellos es ya un algoritmo in-situ. En todos ellos es necesariogestionar una cantidad adicional de memoria proporcional al tamaño de los datos a ordenar... pero de ellos hablaremos en otros artículos.
En este trabajo nos centraremos en ShellSort. Describiremos la idea que subyace detrás del algoritmo, e intentaremos llegar de manera intuitiva al código del algoritmo.




Origen del Shell sort

El ordenamiento Shell (Shell sort en inglés) es un algoritmo deordenamiento. El método se denomina Shell en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(n log2 n) en el peor caso. Esto es mejor que las O (n2) comparaciones requeridas por algoritmos simples pero peor que el óptimoO(n log n). Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.
El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:
1. El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
2. El ordenamiento por inserción es ineficiente, en general, porquemueve los valores sólo una posición cada vez.
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...