5.10. El ordenamiento de Shell¶
El ordenamiento de Shell, a veces llamado “ordenamiento de incremento decreciente”, mejora el ordenamiento por inserción al romper la lista original en varias sublistas más pequeñas, cada una de las cuales se ordena mediante un ordenamiento por inserción. La manera única en que se eligen estas sublistas es la clave del ordenamiento de Shell. En lugar de dividir la lista en sublistas de ítems contiguos, el ordenamiento de Shell usa un incremento i, a veces denominado brecha, para crear una sublista eligiendo todos los ítems que están separados por i ítems.
Este proceso se puede ver en la Figura 6. La lista tiene nueve ítems. Si usamos un incremento de tres, hay tres sublistas, cada una de las cuales puede ordenarse mediante un ordenamiento por inserción. Después de completar estos ordenamientos, obtenemos la lista que se muestra en la Figura 7. Aunque esta lista no está completamente ordenada, ha ocurrido algo muy interesante. Al ordenar las sublistas, hemos acercado los ítems a donde realmente pertenecen.
Figura 6: Un ordenamiento de Shell con incrementos de tres¶
Figura 6: Un ordenamiento de Shell con incrementos de tres
Figura 7: Un ordenamiento de Shell después de ordenar cada sublista¶
Figura 7: Un ordenamiento de Shell después de ordenar cada sublista
La Figura 8 muestra un ordenamiento por inserción final que usa un incremento de uno; en otras palabras, un ordenamiento por inserción estándar. Note que mediante la realización anticipada de los ordenamientos de las sublistas, hemos reducido el número total de operaciones de desplazamiento necesarias para poner la lista en su orden definitivo. Para este caso, sólo necesitamos cuatro desplazamientos más para completar el proceso.
Figura 8: Ordenamiento de Shell: Un ordenamiento por inserción final con incremento de 1¶
Figura 8: Ordenamiento de Shell: Un ordenamiento por inserción final con incremento de 1
Figura 9: Sublistas iniciales para el ordenamiento de Shell¶
Figura 9: Sublistas iniciales para el ordenamiento de Shell
Dijimos antes que la forma en que se eligen los incrementos es la característica única del ordenamiento de Shell. La función mostrada en el ActiveCode 1 utiliza un conjunto diferente de incrementos. En este caso, comenzamos con \(\frac {n}{2}\) sublistas. En la siguiente pasada, se ordenan \(\frac {n}{4}\) sublistas. Eventualmente, se ordena una sola lista con el ordenamiento por inserción básico. La Figura 9 muestra las primeras sublistas para nuestro ejemplo usando este incremento.
La siguiente invocación a la función ordenamientoDeShell muestra las listas parcialmente ordenadas después de cada incremento, siendo el ordenamiento final un ordenamiento por inserción con un incremento de uno.
A primera vista usted podría pensar que un ordenamiento de Shell no puede ser mejor que un ordenamiento por inserción, ya que ejecuta un ordenamiento por inserción completo como último paso. Resulta, sin embargo, que este ordenamiento por inserción final no necesita hacer muchas comparaciones (o desplazamientos) ya que la lista ha sido pre-ordenada mediante ordenamientos por inserción incrementales anteriores, como se describió antes. En otras palabras, cada pasada produce una lista que está “más ordenada” que la anterior. Esto hace que la pasada final sea muy eficiente.
Aunque un análisis general del ordenamiento de Shell está muy por encima del alcance de este texto, podemos decir que tiende a caer entre \(O(n)\) y \(O(n^{2})\), con base en el comportamiento descrito anteriormente. Para los incrementos que se muestran en el Programa 5, el desempeño es \(O(n^{2})\). Cambiando el incremento, por ejemplo usando \(2^{k}-1\) (1, 3, 7, 15, 31 y así sucesivamente), un ordenamiento de Shell puede realizarse en \(O(n^{\frac {3}{2}})\).
Autoevaluación
- [5, 3, 8, 7, 16, 19, 9, 17, 20, 12]
- Cada grupo de números representados por posiciones de índices separados por 3 se clasifican correctamente.
- [3, 7, 5, 8, 9, 12, 19, 16, 20, 17]
- Esta solución es para un tamaño de brecha de dos.
- [3, 5, 7, 8, 9, 12, 16, 17, 19, 20]
- Esta es una lista completamente ordenada, usted ha ido demasiado lejos.
- [5, 16, 20, 3, 8, 12, 9, 17, 20, 7]
- El tamaño de brecha de tres indica que el grupo representado por cada tercer número p.ej. 0, 3, 6, 9 y 1, 4, 7 y 2, 5, 8 se ordenan, no que sean grupos de 3.
Q-3: Dada la siguiente lista de números: [5, 16, 20, 12, 3, 8, 9, 17, 19, 7] ¿Cuál de las siguientes respuestas ilustra el contenido de la lista después de que todo el intercambio está completo para un tamaño de brecha de 3?