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.
Contenido
[ocultar]
1 Descripción
2 Ejemplo
3 Secuencia de espacios
4 Análisis del Costo Computacional
5 Implementación
6 Véase también
7 Fuentes
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
