Unidad 1 Actividad 4 Concepto de Shell

1.
Con lo explicado en el Recurso 5, diseña un esquema descriptivo de la manera cómo

funciona un Shell, en el sistema operativo.
Algoritmo de ordenamiento Shell: El método se denomina así en honor de su inventor Donald

Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor
caso, aunque un cambio menor presentado en el libro de V. Pratt produce una implementación
con un rendimiento de O(n log2 n) en el peor caso. Esto es mejor que las O(n2) comparaciones
requeridas por algoritmos simples pero peor que el óptimo O(n log n).
El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos
observaciones: El ordenamiento por inserción es eficiente si la entrada está "casi ordenada". El
ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una
posición cada vez.
El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados
por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes"
hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de
espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por
inserción, pero para entonces, ya está garantizado que los datos del vector están casi
ordenados.
Descripción.
El algoritmo Shell es una mejora de la ordenación por inserción, donde se van comparando
elementos distantes, al tiempo que se los intercambian si corresponde. A medida que se
aumentan los pasos, el tamaño de los saltos disminuye; por esto mismo, es útil tanto como si
los datos desordenados se encuentran cercanos, o lejanos.
Es bastante adecuado para ordenar listas de tamaño moderado, debido a que su velocidad es
aceptable y su codificación es bastante sencilla. Su velocidad depende de la secuencia de
valores con los cuales trabaja, ordenándolos. El siguiente ejemplo muestra el proceso de forma
gráfica:
Considerando un valor pequeño que está inicialmente almacenado en el final del vector.
Usando un ordenamiento O(n2) como el ordenamiento de burbuja o el ordenamiento por
inserción, tomará aproximadamente n comparaciones e intercambios para mover este valor
hacia el otro extremo del vector.
El Shell sort primero mueve los valores usando tamaños de espacio gigantes, de manera que un
valor pequeño se moverá bastantes posiciones hacia su posición final, con sólo unas pocas
comparaciones e intercambios.
Ejemplo:
Por ejemplo, considere una lista de números como [13 14 94 33 82 25 59 94 65 23 45 27 73 25

39 10]. Si comenzamos con un tamaño de paso de 8, podríamos visualizar esto dividiendo la
lista de números en una tabla con 5 columnas. Esto quedaría así:
Entonces ordenamos cada columna, lo que nos queda:
Cuando lo leemos de nuevo como una única lista de números, obtenemos [ 10 14 73 25 23 13

27 94 33 39 25 59 94 65 82 45]. Aquí, el 10 que estaba en el extremo final, se ha movido hasta
el extremo inicial.
Esta lista es entonces de nuevo ordenada usando un ordenamiento con un espacio de 3

posiciones, y después un ordenamiento con un espacio de 1 posición (ordenamiento por
inserción simple).
Secuencia de espacios.
La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia
incremental funcionaría siempre que el último elemento sea 1. El algoritmo comienza
realizando un ordenamiento por inserción con espacio, siendo el espacio el primer número en la
secuencia de espacios. Continua para realizar un ordenamiento por inserción con espacio para
cada número en la secuencia, hasta que termina con un espacio de 1.
Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un

ordenamiento por inserción ordinario, garantizando que la lista final estará ordenada. La
secuencia de espacios que fue originalmente sugerida por Donald Shell debía comenzar con N /
2 y dividir por la mitad el número hasta alcanzar 1.
Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos
cuadráticos como el ordenamiento por inserción, se puede cambiar ligeramente para disminuir
más el tiempo necesario medio y el del peor caso. Quizás la propiedad más crucial del Shell sort
es que los elementos permanecen k-ordenados incluso mientras el espacio disminuye.
Se dice que un vector dividido en k subvectores esta k-ordenado si cada uno de esos
subvectores esta ordenado en caso de considerarlo aislado. Por ejemplo, si una lista fue 5-
ordenada y después 3-ordenada, la lista está ahora no sólo 3-ordenada, sino tanto 5-ordenada
como 3-ordenada. Si esto no fuera cierto, el algoritmo desharía el trabajo que había hecho en
iteraciones previas, y no conseguiría un tiempo de ejecución tan bajo.
Análisis del Costo Computacional
Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil
analizar su tiempo de ejecución. 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), O(n3 / 2) (usando
los incrementos de Hibbard de 2k − 1), O(n4 / 3) (usando los incrementos de Sedgewick de 9(4i)
− 9(2i) + 1, o 4i + 1 + 3(2i) + 1), o O(nlog2n), y posiblemente mejores tiempos de ejecución no
comprobados. La existencia de una implementación O(nlogn) en el peor caso del Shell sort
permanece como una pregunta por resolver.
Implementación
A continuación, se muestra el Ordenamiento Shell en algunos de los lenguajes de programación

de alto nivel más usados:
 C
//Ordenamiento por método Shell

public static void shellSort(int[] a) {
for ( int increment = a.length / 2;
increment > 0;
increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) {
for (int i = increment; i <>
for (int j = i; j >= increment && a[j - increment] > a[j]; j -= increment) {
int temp = a[j];
a[j] = a[j - increment];
a[j - increment] = temp;
}
}
}
}
 PHP
<?php
//Ordenamiento por Shell
01 <?php
02 function ordenamientoShell($A,$n)
03 {
04 for($inc = 1 ; $inc<$n;$inc=$inc*3+1);
05 while ($inc > 0)
06 {
07 for ($i=$inc; $i < $n; $i++)
08 {
09 $j = $i;
10 $temp = $A[$i];
11 while (($j >= $inc) && ($A[$j-$inc] > $temp))
12 {
13 $A[$j] = $A[$j - $inc];
14 $j = $j - $inc;
15 }
16 $A[$j] = $temp;
17 }
18 $inc/= 2;
19 }
20 return $A;
21 }
22 function main()
23 {
24 $VectorA=array(5,4,3,2,1);
25 $VectorB=ordenamientoShell($VectorA,sizeof($VectorA));
26 for($i=0;$i<sizeof($VectorB);$i++)
27 echo $VectorB[$i]."\n";
28 }
29 main();
30 ?>
 Python
1. #Algoritmo de ordenamiento Shell

2.
3. def shellsort (lista) :
4. """Ordena la lista por metodo Shell, o ShellSort"""
5. incremento=len(lista)/2
6. while (incremento>0) :
7. for i in range(incremento,len(lista)) :
8. j=i
9. temporal=lista[i]
10. while ( (j>=incremento) and (lista[j-incremento]>temporal) ) :
11. lista[j]=lista[j-incremento]
12. j=j-incremento
13. lista[j]=temporal
14. if (incremento==2) : incremento=1
15. else : incremento=int(incremento/2.2)
16. return lista

Unidad 1 Actividad 4 Concepto de Shell

Cargado por

Copyright:

Formatos disponibles

Unidad 1 Actividad 4 Concepto de Shell

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Unidad 1 Actividad 4 Concepto de Shell

Cargado por

Copyright:

Formatos disponibles

1.

Con lo explicado en el Recurso 5, diseña un esquema descriptivo de la manera cómo

Algoritmo de ordenamiento Shell: El método se denomina así en honor de su inventor Donald

Por ejemplo, considere una lista de números como [13 14 94 33 82 25 59 94 65 23 45 27 73 25

Entonces ordenamos cada columna, lo que nos queda:

Cuando lo leemos de nuevo como una única lista de números, obtenemos [ 10 14 73 25 23 13

Esta lista es entonces de nuevo ordenada usando un ordenamiento con un espacio de 3

Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un

Análisis del Costo Computacional

A continuación, se muestra el Ordenamiento Shell en algunos de los lenguajes de programación

//Ordenamiento por método Shell

1. #Algoritmo de ordenamiento Shell

También podría gustarte