Método de Ordenamiento Shell

Universidad Nacional Autónoma de Nicaragua
UNAN – Managua
Recinto Universitario “Rubén Darío”
Facultad de Ciencias e Ingenierías
Departamento de Computación




Ordenamiento

“Método de ordenamiento Shell”



Asignatura:
Algoritmos y Estructuras de Datos II


Profesora:
Msc. Amparo Herrera.


Autor:
Br. Carlos Javier Reyes Espinoza.






Miércoles, 07 de octubre de 2015.
Índice

Pág.
IIntroducción ……………………………………………………………. 1
II Objetivos ……………………………………………………………. 2
III Marco Teórico ……………………………………………………………. 3
IV Algoritmo de Ordenación Shell ……………………………………. 4
V Análisis de eficiencia:
a Ventajas ……………………………………………………………. 5
b Desventajas ……………………………………………………………. 5
VI Conclusiones ……………………………………………………………. 6
VII Bibliografía ……………………………………………………………. 7
VIII Programa Fuente……………………………………………....... 8 - 9
Introducción

Muchas de nuestras actividades de la vida diaria, estudiantil o laboral, requieren que una colección de datos o elementos dispongan de un orden específico para su proceso. Es por ello que uno de los trabajos más comunes que realiza un pc es la ordenación.
La ordenación consistente en disponer una estructura de datos en algún determinado orden. Los elementos, se pueden ordenar en orden creciente odecrecientes según su valor. Existen diferentes algoritmos de ordenación elementales presentan diferencias entre ellos que los convierten en más o menos eficientes y prácticos según sea la rapidez y eficiencia demostrada por cada uno de ellos, entre los algoritmos más simples se encuentra el Método Shell Sort o Método de Ordenamiento Shell, una variación del método por inserción directa sobre elcuál se desarrolla este documento.

Objetivos

Conocer e Interpretar conceptos teóricos sobre el Método de Ordenamiento Shell.
Identificar eficiencia, ventajas y desventajas en el uso del Método de Ordenamiento Shell.
Implementar algoritmo sobre Método de Ordenamiento Shell en un problema práctico.

Marco Teórico

Ordenación Shell
La ordenación Shell o Shell Sort debe el nombre a su inventor, Donald.L. Shell. Se suele denominar también ordenación por inserción con intervalos decrecientes. Se considera que es una mejora del método de inserción directa.
El método de ordenación 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 la posición que debe ocupar. Los pasosmúltiples sobre los elementos se hacen con tamaños de espacio cada vez más pequeños y el último paso del método es un simple ordenamiento por inserción directa, pero para entonces, los elementos de arreglo ya casi están ordenados.
Para determinar el tamaño de los intervalos (saltos) constantes, el primero debe ser generado a partir del tamaño del arreglo entre dos, obteniendo solo su parte entera de ladivisión o redondeando el resultado de la misma, y posteriormente ir reduciendo a la mitad el incremento en cada repetición, hasta que el incremento sea un uno.

Algoritmo de ordenación Shell

Los pasos a seguir por el algoritmo para una lista de n elementos:

1. Se divide la lista original en n/2 grupos de dos, considerando un incremento o salto entre los elementos de n/2.
2. Se clasifica cadagrupo por separado, comparando las parejas de elementos y si no están ordenados se intercambian.
3. Se divide ahora la lista en la mitad de grupos (n/4), con un salto entre los elementos también mitad (n/4), y nuevamente se clasifica cada grupo por separado.
4. Así sucesivamente, se sigue dividiendo la lista en la mitad de grupos que en el recorrido anterior con un salto decreciente en la mitad que elsalto anterior, y luego clasificando cada grupo por separado.
5. El algoritmo termina cuando el tamaño del salto es 1.

La secuencia de saltos que fue originalmente sugerida por Donald Shell debía comenzar con N/2 y dividir por la mitad el número hasta alcanzar 1.
La propiedad más importante del Shell Sort es que los elementos permanecen ordenados incluso...