Shell

S
H
E
L
L
S
O
R
T

## METODO SHELL SORT

Algoritmo de ordenamiento Shell: El método se denomina así en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso, aunque 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 óptimo O(n log n).
El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones: El ordenamiento por inserción es eficiente si la entrada está "casi ordenada". El ordenamiento por inserción es ineficiente, en general, 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 simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.

### 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.
- Necesita que el tiempo de acceso a cualquier dato sea constante (es decir, fue ideado para trabajar con arrays, arrays de referencias o punteros, etc…).
- No es estable: dados dos elementos que al compararlos sean “iguales” -es decir, que pueden ir indistintamente en la misma posición, 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 la burbuja, 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 es posible 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.

  ### Ventajas y Desventajas

  • Es uno de los algoritmos más rápidos.
  • No requiere memoria adicional.
  •Mejor rendimiento que el método de inserción clásico.
  •Fácil implementación.
  • Lento en cuanto a los siguientes métodos de ordenamiento.
  •Realiza numerosas comparaciones e intercambios.

  ### ALGORITMO DE ORDENAMIENTO SHELL SORT

  El ShellSort ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo o lista original. El valor K es llamado incremento.
  Después de que los primeros K subgrupos han sido ordenados (generalmente se utiliza inserción directa), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K, como en la grafica de arriba.

  ### EJEMPLO

  Ordenar el siguiente arreglo de numeros por el metodo SHELL SORT: 4, 20, 64, 8, 0, 33, 41, 56, 18, 10.

  #### SOLUCIÓN

  ## VIDEO COMPLEMENTARIO

  #### Método de ordenamiento Shell

  ## REFERENCIAS ELECTRONICAS

- https://danielandres25.wordpress.com/unidad-1/algoritmos-de-busqueda-y-ordenamiento/metodo-de-ordenamiento-shell-sort/
- http://algoritmobasico.blogspot.mx/2015/11/metodo-de-ordenamiento-shell.html
- https://prezi.com/il8mtjd1zb8a/metodo-de-ordenamiento-shell/
- https://www.ecured.cu/Algoritmo_de_Ordenamiento_Shell