El método de ordenación Shell debe su nombre a su inventor, Donald Shell, y fue uno de los primeros algoritmos de ordenamiento en romper la barrera del tiempo cuadrático.
Es una mejora del método de inserción directa, utilizado cuando el array tiene un gran número de elementos.
Cualquier algoritmo de ordenación que intercambia elementos adyacentes (como los algoritmos burbuja, selección o inserción) tiene un tiempo promedio de ejecución de orden cuadrático (n2). El método Shell mejora este tiempo comparando cada elemento con el que está a un cierto número de posiciones llamado salto, en lugar de compararlo con el el que está justo a su lado. Este salto es constante, y su valor inicial es N/2 (siendo N el número de elementos, y siendo división entera).
Se van dando pasadas con el mismo salto hasta que en una pasada no se intercambie ningún elemento de sitio. Entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así sucesivamente hasta que el salto vale 1.
El método Shell de ordenación en Java para ordenar un array A de enteros es el siguiente:
public static void shell(int A[]){
int salto, aux, i;
boolean cambios;
for(salto=A.length/2; salto!=0; salto/=2){
cambios=true;
while(cambios){ // Mientras se intercambie algún elemento
cambios=false;
for(i=salto; i< A.length; i++) // se da una pasada
if(A[i-salto]>A[i]){ // y si están desordenados
aux=A[i]; // se reordenan
A[i]=A[i-salto];
A[i-salto]=aux;
cambios=true; // y se marca como cambio.
}
}
}
}
Ejemplo de ejecución:
Con sólo 6 intercambios se ha ordenado el array, cuando por inserción se necesitaban muchos más. El rendimiento del método Shell de ordenación es bastante aceptable, aún para el caso de un número de elementos muy grande. Se ha comprobado que el tiempo de ejecución promedio es de O(n2/3) para la mayoría de las secuencias de salto.
0 Comentarios