Algoritmo de Ordenamiento Shell
| ||||||
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.
Sumario
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
Véase también
- Algoritmo de ordenamiento
- Algoritmo de búsqueda
- Algoritmo de Kruskal
- Algoritmo de Euclides
- Algoritmo de Prim
- Algoritmo de Boruvka
- Algoritmo de Gutmann
- Algoritmo criptográfico
- Algoritmo de Ordenamiento Burbuja
- Algoritmo
- Algoritmo genético
- Algoritmo de ordenamiento por selección
- Algoritmo de árboles de decisión de Microsoft
- Algoritmo de Búsqueda Heurística A*
- Algoritmo asimétrico
Fuentes
- Aprenda C/C++.
- Estructuras de datos.
- Wikipedia.
