Metodo de shell

Método 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 muy sencillo 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 deinserción directa.
CARACTERÍSTICAS
* Se trata de un algoritmo de ordenación interna. Al igual que cualquier otro de ordenación interna (los datos están en memoria principal) podría utilizarse para ordenación externa (en memoria secundaria) siempre y cuando se disponga de acceso aleatorio, pero el algoritmo no fue ideado para eso.
* Se basa en comparaciones e intercambios
* No esestable: dados dos elementos que al compararlos sean "iguales" no mantienen necesariamente el orden relativo inicial entre ellos
* El estudio de su complejidad no es trivial, sino todo lo contrario. La implementación original de Shell tiene una complejidad en el peor caso de O(n2), aunque en un caso promedio o en casos típicos comprobados empíricamente, los resultados son mucho mejores que con laburbuja, selección directa o inserción directa, cuya complejidad en el peor caso también es del orden de O(n2).
* sin embargo, optimizaciones posteriores han logrado reducir esa cota... Por ejemplo, con la optimización de Robert Sedgewick se llega a O(n4/3), y con la propuesta por Vaughan Pratt se llega al orden de O(n log2n).
En 1992, Greg Plaxton, Bjorn Poonen y Torsten Suel prueban que esposible incluso rebajar aún más esas cotas.
* En cierto modo, puede considerarse una ampliación del algortimo de inserción directa, con lo cual, conviene tenerlo claro antes de meterse con el de Shell.
* No es un algoritmo en-línea.
* A diferencia del algoritmo de ordenación por inserción, este algoritmo intercambia elementos distantes. Es por esto que puede deshacer más de una inversiónen cada intercambio, hecho del cual nos aprovechamos para ganar velocidad.
* La velocidad del algoritmo dependerá de una secuencia de valores (llamados
* incrementos, de los cuales hablaremos más abajo) con los cuales trabaja utilizándolos como distancias entre elementos a intercambiar. Veremos que con algunas secuencias podremos obtener ordenes de tiempo de ejecución en el peor caso deO(n2), O(n^(3/2)) y O(n^(4/3)).
* Se considera la ordenación de Shell como el algoritmo más adecuado para ordenar entradas de datos moderadamente grandes (decenas de millares de elementos) ya que su velocidad, si bien no es la mejor de todos los algoritmos, es aceptable en la práctica y su implementación (código) es relativamente sencillo

Definicion de Secuencia k-ordenada. Decimos queuna secuencia A de n elementos está k-ordenada(siendo k un natural) si, para todo i de [0,n] se cumple que los elementos A[i + hk] están ordenados, siendo h un entero y siempre que el índice i+hk esté en [0,n].
El algoritmo de ordenación de Shell lo que hace en realidad es tomar una secuencia de
incrementos h1, h2, ..., hp y en la etapa k-esima realizar una hk-ordenación de los datos.
La únicacondición que debe respetar la secuencia de incrementos es hp=1 de modo tal que en la última etapa se hace una 1-ordenación (o sea una ordenación normal).
El Shell 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, engeneral, porque mueve 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 es un...