Pedirle a un ordenador que haga algo intuitivamente es, de momento, bastante

complicado, así que sustituiremos la intuición por un procedimiento mecánico más o menos

ingenioso.Veamos el siguiente arreglo:

74, 14, 21, 44, 38, 97, 11, 78, 65, 88, 30

Shell nos propone que hagamos sobre el arreglo una serie de ordenaciones basadas en la inserción directa, pero dividiendo el arreglo original en varios sub-arreglo tales que cada elemento esté separado k elementos del anterior (a esta separación a menudo se le llama salto o gap)... Se debe empezar con k=n/2, siendo n el número de elementos de arreglo, y utilizando siempre la división entera.... después iremos variando k haciéndolo más pequeño mediante sucesivas divisiones por 2, hasta llegar a k=1.Pero vamos a ello... En nuestro ejemplo, n=11 (porque hay 11 elementos). Así que k=n/2=11/2=5

Empezamos con k=5. Así pues, vamos a dividir nuestro arreglo original en 5 sub-arreglo, en los cuales, sus

elementos estarán separados por 5 lugares del arreglo original (el salto o gap es 5).

Vamos a hacerlo con colores. Tomamos el primer elemento (el 74) contamos 5 lugares y tomamos también

otro elemento (el 97) volvemos a contar 5 y tomamos otro (el 30) y acabamos porque se nos acaba el arreglo.El primer sub-arreglo con k=5 es el formado por 74, 97 y

30. Vamos a pintarlos en rojo

74, 14, 21, 44, 38, 97, 11, 78, 65, 88, 30

Ahora, ordenaremos los elementos del sub-arreglo rojo pero sólo entre ellos, utilizando el algoritmo de Inserción directa.

 

30, 14, 21, 44, 38, 74, 11, 78, 65, 88, 97 

Fíjate qué curioso. El 30, un elemento relativamente pequeño se ha ido hacia el principio y el 97 hacia el final... ¡pero dando saltos (gap) de 5 en 5 lugares! Cada uno ha avanzado en saltos de 5 hacia una posición cercana a su

ubicación definitiva.

Fíjate qué curioso. El 30, un elemento relativamente pequeño se ha ido hacia el principio y el 97 hacia el final... ¡pero dando saltos (gap) de 5 en 5 lugares! Cada uno ha avanzado en saltos de 5 hacia una posición cercana a su

ubicación definitiva.Formemos ahora otro sub-arreglo con salto k=5... partiendo

del segundo elemento (el 14) y contando 5 (tomamos también el 11) y ya está, porque se acaba el arreglo.

 

30, 14, 21, 44, 38, 74, 11, 78, 65, 88, 97

Vamos a ordenarlos entre ellos con Inserción directa... el 11 primero y el 14 después.

 

30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97

Ahora a por otro... el 21 y el 78  

30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97 

Están en orden entre ellos, así que se quedan como están.

Ahora le toca al sub-arreglo formado por el 44 y el 65  

30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97 

Que también están en orden entre ellos... y finalmente el 38 y el 88, que también están en orden.

30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97

Hemos formado 5 sub-arreglos en los cuales los elementos están separados por 5 lugares (porque k=5). Hemos ordenado cada sub-arreglo por separado utilizando

inserción directa, y hemos logrado que cada elemento se dirija hacia su ubicación definitiva en pasos de 5 lugares.Por supuesto, no hemos terminado todavía, pero resulta

evidente que algunos elementos, como el 30, el 97 o el 11 han dado un gran salto y que no deben andar muy lejos

de su sitio final.

Decimos ahora que el arreglo está 5-ordenado. 

Para continuar con el algoritmo, debemos ir reduciendo progresivamente k dividiéndolo sucesivamente por 2 y k-

ordenando los sub-arreglos que nos salgan (recuerda que nos salen k sub-arreglo). Cuando lleguemos a k=1

habremos terminado. 

Pero de momento, nuestra k valía 5, así que ahora k←k/2=5/2=2

 Nuestra nueva k vale 2. Repetimos todo el tinglado, pero ahora nos saldrán 2 sub-arreglo cuyos elementos están

separados por 2 lugares.

El primero (en marrón) y el segundo (en verde):

30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97

Ordenamos por un lado los marrones entre ellos y los verdes entre ellos... es decir, 2-ordenamos el arreglo (curiosamente,

los verdes ya están ordenados.... probablemente ha contribuido a ello la 5-ordenación que ya hemos hecho. En ese caso, la ordenación ha requerido muy poco esfuerzo)

 

14, 11, 21, 44, 30, 74, 38, 78, 65, 88, 97

Ahora, cada número está mucho más cerca de su posición definitiva... El arreglo está 2-ordenado... pero sigue

también 5-ordenado. No hemos perdido el trabajo que hicimos cuando k era 5.

 Finalmente, calculamos un nuevo k dividiendo el que

tenemos entre 2. k←k/2=2/2=1Hemos llegado a k=1. Cuando k es 1 sólo podemos

obtener 1 sub-arreglo cuyos elementos están separados 1 posición: el propio arreglo original. Dicho de otra manera...

cuando k es 1, el algoritmo de Shell se comporta exactamente igual que el de inserción directa sobre todo

el arreglo.

Sin embargo, las k-ordenaciones que hemos hecho (con k=5 y k=2) han hecho que cada elemento se aproximase

con saltos de 5 y luego de 2 posiciones hacia su ubicación definitiva. Ahora que k=1 y que vamos a aplicar el

algoritmo de inserción directa tal cual, haremos muchas menos comparaciones e intercambios que si lo

hubiéramos aplicado con en arreglo tal como lo teníamos al empezar. El algoritmo de inserción directa se comporta tanto mejor cuanto más cerca está cada elemento de su

sitio definitivo. 

Finalmente, el arreglo queda de ésta manera: 

11, 14, 21, 30, 38, 44, 65, 74, 78, 88, 97 

Cada elemento descolocado ha tenido que moverse pocos lugares. Muchos de ellos ni siquiera se han movido.