Shell Sort
Páginas: 5 (1025 palabras)
Publicado: 31 de octubre de 2012
DESCRIPCIÓN DEL MÉTODO • El Shell Sort ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado incremento.
DESCRIPCIÓN DEL MÉTODO
• Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa. • Para ilustrar mejor el proceso se tomará como ejemploel vector
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 deelementos 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 por5 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 suubicació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-arregloformado 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, yhemos 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 reduciendoprogresivamente k dividiéndolo sucesivamente por 2 y kordenando 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...
DESCRIPCIÓN DEL MÉTODO
• Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa. • Para ilustrar mejor el proceso se tomará como ejemploel vector
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 deelementos 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 por5 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 suubicació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-arregloformado 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, yhemos 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 reduciendoprogresivamente k dividiéndolo sucesivamente por 2 y kordenando 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...
Leer documento completo
Regístrate para leer el documento completo.