Método de ordenamiento shell

Método de Ordenamiento Shell

1. Método de Ordenamiento Shell Estructura de Archivos

2. Creado por Donald Shell , que lo publicó en la revista  Communications of the ACM   en 1959 . Es un algoritmo de ordenación interna, se basa en comparaciones e intercambios . Aunque también puede realizar ordenación externa. Es una versión mejorada del método de inserción directa . Introducción

3. En el método se propone que las comparaciones se efectúen con saltos de mayor tamaño, pero con incrementos que sean saltos de mayor tamaño pero con incrementos decrecientes, así los elementos quedarán ordenados en el arreglo.  Modo de Trabajar

4. ( INT, I y AUX son variables de tipo entero. BAND es una variable de tipo booleano ) 1.- Hacer INT  N +1. 2.- Mientras (INT > 1) Repetir Hacer INT  parte entera (INT /2) y BAND  VERDADERO. 2.1 .- Mientras (BAND == VERDADERO) Repetir. Hacer BAND  FALSO e I  1. 2.1.1 .- Mientras ((I + INT) <= N) Repetir. 2.1.1.1 .- Si A [I] > A[I + INT] Entonces. Hacer AUX  A[I], A[I]  A[I + INT], A[I + INT]  AUX y BAND  VERDADERO. 2.1.1.2 .- {Fin del condicional del paso 2.1.1.1} Hacer I  I + 1. 2.1.2 .- {Fin del ciclo del paso 2.1.1} 2.2 .- { Fin del ciclo del paso 2.1} 3.- { Fin del ciclo del paso 2} Pseudocódigo

5. Representación Gráfica

6. El análisis de eficiencia es un problema complicado y aun no resuelto. Nadie ha sido capaz de establecer la mejor secuencia de incrementos cuando N es muy grande .   Eficiencia

7. En 1969 Pratt descubrió que el tiempo de ejecución del es de orden n*(log n)2 . Unas pruebas realizadas para saber la mejor secuencia de intervalos cuando el número de elementos es igual a 8 dieron como resultado que la mejor secuencia es un intervalo de 1, pero esto equivale al método de inserción directa.   Complejidad

8. Implementación (Código)

9. Gracias por su Atención