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

Imágen de pdf Análisis del algoritmo ShellSort

Análisis del algoritmo ShellSortgráfica de visualizaciones

Actualizado el 22 de Mayo del 2020 (Publicado el 12 de Abril del 2018)
571 visualizaciones desde el 12 de Abril del 2018
303,5 KB
16 paginas
Creado hace 12a (30/11/2007)
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
  • Links de descarga
http://lwp-l.com/pdf10357

Comentarios de: Análisis del algoritmo ShellSort (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad