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.

../_images/shellsortA.png

Figura 6: Un ordenamiento de Shell con incrementos de tres

Figura 6: Un ordenamiento de Shell con incrementos de tres
../_images/shellsortB.png

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.

../_images/shellsortC.png

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
../_images/shellsortD.png

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

    Q-12: 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?
  • (A) [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.
  • (B) [3, 7, 5, 8, 9, 12, 19, 16, 20, 17]
  • Esta solución es para un tamaño de brecha de dos.
  • (C) [3, 5, 7, 8, 9, 12, 16, 17, 19, 20]
  • Esta es una lista completamente ordenada, usted ha ido demasiado lejos.
  • (D) [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.
Next Section - 5.11. El ordenamiento por mezcla