Estructuras De Datos Shell

Ordenamient o Shell Sort Erika Pulido Moreno Código: 624517 Oscar Darío Alonso Código: 624497

Es una mejora del método de inserción directa que se utiliza cuando el número de elementos a ordenar es grande. El método se denomina “shell” –en honor de su inventor Donald shell – y también método de inserción con incrementos decrecientes. En el método de clasificación por inserción, cada elemento se compara con los elementos contiguos de su izquierda, uno tras otro. Si el elemento a insertar es más pequeño.

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.

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 subarreglo). 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=1 Hemos 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.