Equipo :
Castrejón Martínez Yair Eduardo
Flores Salgado Berenice
López Moreno Orlando Dante
Antecedentes
La ordenación Shell Sort, debe su nombre a su diseñador Donald L. Shell, ingeniero y matemático. Fue creado en 1959 y publicado por la revista “Communications of the ACM (Association for Computer Machinery)”.
Otro nombre que suele recibir es Ordenación por inserción con incrementos decrecientes. El método es considerado una mejora de los métodos de inserción directa, mejora el método de inserción ordenado por romper la lista original en sub-listas más pequeñas, con la cual cada una es ordenada usando un método de inserción.
Algoritmo de inserción
- Para k > 1, Se elige el primer elemento de la lista y con el valor se suma a la posición actual de la lista para revisar ese elemento, en caso de que el elemento que se encuentre a la izquierda sea menor se hace el intercambio, una vez realizado esto se procede a comparar la siguiente posición de la lista.
- Para k=1, Se vuelven a comparar los elementos iniciando desde la izquierda con su contiguo, si hay un cambio se retrocede en la lista para comparar nuevamente, en caso de no haber cambio procede con la lista hasta llegar al final.
Algoritmo
Se divide la lista original en k=n/2 grupos de dos, considerando un incremento (salto) entre todos los elementos de k.
Cada grupo es clasificado por separado, comparando las parejas de los elementos y si estos no están ordenados se intercambian.
Se divide la lista a la mitad k=k/2 (n/4), y nuevamente se va a clasificar cada grupo por separado. Sucesivamente se sigue dividiendo la lista en la mitad de grupos que en el recorrido anterior, con un salto decreciente en la mitad que el salto anterior y después clasificando cada grupo por separado.
El algoritmo se termina cuando k=1 y se haga la ultima comparación siguiendo el algoritmo de inserción.
Cada grupo es clasificado por separado, comparando las parejas de los elementos y si estos no están ordenados se intercambian.
Se divide la lista a la mitad k=k/2 (n/4), y nuevamente se va a clasificar cada grupo por separado. Sucesivamente se sigue dividiendo la lista en la mitad de grupos que en el recorrido anterior, con un salto decreciente en la mitad que el salto anterior y después clasificando cada grupo por separado.
El algoritmo se termina cuando k=1 y se haga la ultima comparación siguiendo el algoritmo de inserción.
Tiempo de ejecución
Big O
Omega
Aplicación
Actualmente Shell sort rara vez se utiliza para aplicaciones serias. Debido a su mayor número de operaciones. Sin embargo, ya que necesita de código relativamente corto y no utiliza la pila de llamadas, algunas implementaciones con la función qsort en la biblioteca estándar de C esta dirigida a los sistemas integrados y se termina siendo usado en lugar de quicksort. ShellSort, por ejemplo, que se utiliza en la biblioteca uClibc. Por razones similares, una implementación de ShellSort está presente en el kernel de Linux. ShellSort también puede servir como un algoritmo de sub-especie de introspectiva, para ordenar sub-arreglos cortos y para evitar una desaceleración patológica cuando la profundidad de recursión supera un límite determinado.
Ventajas y desventajas
Bibliografía
Algoritmos y estructura de datos "Una perspectiva en C" Autor Luis Joyanes Aguilar,Ignacio Zahonero Martinez
C++ Data Estructures, Nell Dale, David Tegure, Jones & Bartlett
Mastering Algorithms with C, Kyle Loudon, O' Reilly, 1era Edicion.
Fundamentos de programación y estructuras de datos y objetos, LUIS JOYANES AGUILAR , S.A. MCGRAW-HILL / INTERAMERICANA DE ESPAÑA, 2003
C++ Data Estructures, Nell Dale, David Tegure, Jones & Bartlett
Mastering Algorithms with C, Kyle Loudon, O' Reilly, 1era Edicion.
Fundamentos de programación y estructuras de datos y objetos, LUIS JOYANES AGUILAR , S.A. MCGRAW-HILL / INTERAMERICANA DE ESPAÑA, 2003
