PRESENTADO POR:
JOHAAR LEZCANO
JOSEPH SERRACÍN
SHELL SORT
ANÁLISIS DEL ALGORITMO
SHELLSORT
• Denominado así por su desarrollador
Donald Shell (1959), ordena una
estructura de una manera similar a la del
Bubble Sort, sin embargo no ordena
elementos adyacentes sino que utiliza una
segmentación entre los datos. Esta
segmentación puede ser de cualquier
tamaño de acuerdo a una secuencia de
valores que empiezan con un valor grande
y van disminuyendo hasta llegar al '1'.
DESCRIPCIÓN DEL MÉTODO
• El ShellSort ordena subgrupos de elementos
separados K unidades (respecto de su posición
en el arreglo) del arreglo original. El valor K es
llamado incremento.
• Después de que los primeros K subgrupos han
sido ordenados (generalmente utilizando
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.
DESCRIPCIÓN DEL MÉTODO
• Cuando el incremento toma un valor de 1,
todos los elementos pasan a formar parte
del subgrupo y se aplica inserción directa.
• Para ilustrar mejor el proceso que sigue el
procedimiento ShellSort, se tomará como
ejemplo el vector :{6,1,5,2,3,4,0}.
5041415>6246 >>12453403
2
02
6 1 25
4 32
6 43 54 60
0
4
Salto 13
Dev C++
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
• Lista Original n=7.
• Intervalo Inicial: n/2=7/2=3 6 1 5 2 3 4 0
– Intervalos Siguientes=IntervaloAnterior/2
• Se compara a[i] con a[i+Intervalo]
– Si No Están Ordenados Entonces CAMBIARLOS
Paso Intervalo Parejas que Intercambian por La Lista Queda
estar desordenados
1 3 (6,2)= 2, 1, 5,6, 3, 4, 0
(5,4)= 2, 1, 4,6, 3,5, 0 2, 1, 4,0, 3,5, 6
(6;0)=2, 1, 4,0, 3,5, 6
2 3 (2, 0)=0, 1, 4,2, 3,5, 6 0, 1, 4,2, 3,5, 6
3 3 Ninguno 0, 1, 4,2, 3,5, 6
4 3/2=1 (4, 2)=0, 1, 2,4, 3,5, 6 0, 1, 2,3, 4,5, 6
(4, 3)= 0, 1, 2,3,4,5, 6
5 1 Ninguno Lista Ordenada
void ordenacionShell(int a[], int n)
{
int i, j, k, intervalo = n / 2;
int temp;
while (intervalo > 0)
{
for (i = intervalo; i ≤ n; i++)
{
j = i - intervalo;
while (j >= 0)
{
k = j + intervalo; //queda k=i;
if (aj <= ak) j = -1; /*termina el bucle, par ordenado */
else
{
temp = a[j];
a[j] = a[k];
a[k] = temp;
j -= intervalo;
}
} El 1er while:
} Log2n El for: n
intervalo = intervalo / 2; F(n)=n*Log2(n)
}
}
COMPLEJIDAD
• Dependiendo de la elección de la secuencia de
espacios, Shell sort tiene un tiempo de ejecución
en el peor caso de O(n2) (usando los incrementos
de Shell que comienzan con 1/2 del tamaño del
vector y se dividen por 2 cada vez
• La existencia de una implementación O(nlogn) en
el peor caso del Shell sort permanece como una
pregunta por resolver.
• Hibbard (2k − 1) se escogen : EJ: 15 7 3 1.
En este caso en el caso peor el costo es de
n1.3 y en el promedio n1.2
• Sedgewick propuso otras secuencias (9(4i) −
9(2i) + 1, ó 4i + 1 + 3(2i) + 1), EJ: 1, 5, 19, 41,
109... ,en las cuales el costo en el peor caso
es n4/3 y en el promedio n7/6
COMPLEJIDAD EXPERIMENTAL
• La grafica se obtuvo con las siguientes
condiciones de entrada:
• Aleatorio: Tiempo de ejecución para 50 tiempos
generados de manera aleatoria, con
incrementos de 2000 en el tamaño del vector.
• Ordenado: Tiempo de ejecución para 50
arreglos ordenados anticipadamente.
Incrementos de 2000.
• Desordenado: Tiempo de ejecución para 50
arreglos que contienen datos ordenados de
Mayor a Menor. Incrementos de 2000.
COMPLEJIDAD EXPERIMENTAL
VENTAJAS DEL ALGORITMO
SHELLSORT
• Es un algoritmo muy simple teniendo un
tiempo de ejecución aceptable .
• Es uno de los algoritmos más rápidos.
• No requiere memoria adicional.
DESVENTAJAS DEL ALGORITMO
SHELLSORT
• Su complejidad es difícil de calcular y
depende mucho de la secuencia de
incrementos que utilice.
• ShellSort es un algoritmo no es estable
porque se puede perder el orden relativo
inicial con facilidad .
CONCLUSIONES
• El tiempo que requiere este algoritmo
depende siempre de qué sucesión de
Incrementos se use.
• Es importante recalcar que es de gran
ayuda realizar una prueba experimental
del algoritmo, debido a que el análisis
anteriormente planteado se fundamenta
con datos reales, que sustentan la
complejidad encontrada.
GRACIAS
