PDF de programación - Análisis del algoritmo ShellSort

PRESENTADO POR:

BALCAZAR RENGIFO. ALBERTO

PAYÁN. LEIDY VIVIANA

ORDOÑEZ G. YULI ANDREA

NUÑEZ. JESSICA ALEAN

SHELL SORT

ANÁLISIS DEL ALGORITMO

SHELLSORT

ordena

(1959),

• Denominado así por su desarrollador
una
Donald Shell
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.

ordenados

(generalmente

• Después de que los primeros K subgrupos han
sido
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}.

1 > 3
6 > 0
2 > 0
5 > 4
0 > 11 > 4
4 > 2
5> 6
6 > 2
4 > 3
4 > 5

6 1 5 2 3 4 0
2
0
6

60
2 4
4
3

42

5

Salto 3
Salto 1

Dev C++

• Lista Original n=7.
•

Intervalo Inicial: n/2=7/2=3
– Intervalos Siguientes=IntervaloAnterior/2

a[0] a[1] a[2] a[3] a[4]

a[5]

a[6]

6

1

5

2

3

4

0

• 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

(6,2)= 2, 1, 5,6, 3, 4, 0
(5,4)= 2, 1, 4,6, 3,5, 0
(6;0)=2, 1, 4,0, 3,5, 6

(2, 0)=0, 1, 4,2, 3,5, 6

Ninguno

3

3

3

3/2=1

(4, 2)=0, 1, 2,4, 3,5, 6
(4, 3)= 0, 1, 2,3,4,5, 6

1

Ninguno

1

2

3

4

5

2, 1, 4,0, 3,5, 6

0, 1, 4,2, 3,5, 6

0, 1, 4,2, 3,5, 6

0, 1, 2,3, 4,5, 6

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 (a[j] <= a[k]) 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
F(n)=n*Log2(n)

}

intervalo = intervalo / 2;
}

}

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

condiciones de entrada:

las siguientes

• Aleatorio: Tiempo de ejecución para 50 tiempos
con

generados
incrementos de 2000 en el tamaño del vector.

de manera

aleatoria,

• Ordenado: Tiempo de ejecución para 50
anticipadamente.

ordenados

arreglos
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
la secuencia de

depende mucho 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
la
complejidad encontrada.

reales, que sustentan

GRACIAS