
Ordenamiento Shell
Algoritmo de ordenación que generaliza la ordenación por inserción comparando elementos separados por una distancia que se reduce paso a paso.
- Año
- 1959
- Protagonistas
- Donald Shell
- Sección
- Informática
Historia
El ordenamiento Shell es un algoritmo para ordenar una lista de datos, es decir, para colocarlos de menor a mayor. Su interés está en que resuelve con bastante rapidez un problema que, con métodos sencillos, exige muchísimas comparaciones cuando la lista es larga. Su idea central es poner en orden primero elementos que están lejos entre sí, de modo que los valores mal colocados den saltos grandes hacia su posición correcta.
Antes de Shell, los métodos habituales eran la ordenación de burbuja y la ordenación por inserción. La ordenación por inserción funciona muy bien cuando la lista ya está casi ordenada, pero es lenta en general, porque cada elemento solo avanza una posición cada vez. Si un valor pequeño está al final de una lista larga, puede necesitar casi tantos pasos como elementos hay para llegar al principio. Donald Shell observó que, si se comparan elementos separados por un espacio de varias posiciones y se ordenan así, los valores se desplazan mucho más deprisa.
El método funciona por pasadas. En cada pasada se toma un espacio o salto, y se ordenan por inserción los subconjuntos formados por los elementos que quedan separados por ese salto. Puede imaginarse como colocar la lista en una tabla con tantas columnas como indica el salto, ordenar cada columna y leer de nuevo la tabla como una sola lista. Después se repite con un salto más pequeño. Al final el salto vale 1, y se hace una ordenación por inserción normal, pero para entonces la lista ya está casi ordenada, así que esa última pasada cuesta poco. Lo que importa es que, al reducir el salto, las pasadas anteriores no se deshacen: una lista ordenada con un salto de 5 sigue ordenada con cada subconjunto de salto 5 incluso después de ordenar con salto 3.
Shell publicó el método en 1959. La secuencia de saltos que propuso comenzaba en la mitad del tamaño de la lista y la dividía por dos hasta llegar a 1. Esa elección mejoraba mucho a los métodos cuadráticos, pero se descubrió que en ciertos casos podía seguir siendo lenta, con un tiempo de ejecución del peor caso de orden n al cuadrado. Por eso, con los años se propusieron otras secuencias. Vaughan Pratt demostró que, con una pequeña variación, el peor caso mejora hasta un orden n log al cuadrado de n, aunque a costa de un método más complejo. Robert Sedgewick y otros investigadores propusieron secuencias que mejoran los tiempos en la práctica, y Marcin Ciura halló por experimentación una secuencia que da buenos resultados con listas de tamaño moderado.
El análisis teórico del método resultó ser muy difícil, y sigue habiendo preguntas abiertas, como si existe una variante que alcance en el peor caso el tiempo óptimo de los mejores algoritmos de comparación. Aun así, su sencillez lo hizo popular durante décadas, sobre todo en sistemas con poca memoria, porque ordena en el mismo vector sin necesitar espacio adicional significativo. Hoy en día las bibliotecas estándar suelen usar algoritmos más rápidos en general, como variantes de ordenación rápida o por mezcla, pero el ordenamiento Shell sigue enseñándose como ejemplo de cómo una idea sencilla, comparar elementos alejados, puede transformar un método lento en otro bastante eficiente.
Cronología
- 1959Donald Shell publica el método, que lleva su nombre.
- 1959Shell propone una secuencia de saltos que empieza en la mitad del tamaño de la lista y se divide por dos.
- 1971Vaughan Pratt muestra que una pequeña variación reduce el peor caso a un orden n log al cuadrado de n.
- 1986Robert Sedgewick propone secuencias de saltos que mejoran el rendimiento en la práctica.
- 2001Marcin Ciura publica una secuencia de saltos hallada por experimentación, con buenos resultados en listas de tamaño moderado.
Curiosidades y anécdotas
Sin relación con las conchas
Pese a su nombre, el método no tiene nada que ver con las conchas: el nombre viene del apellido de su inventor.
Un nombre discutido
Algunos textos antiguos lo llaman ordenación Shell-Metzner, por Marlene Metzner Norton, pero ella declaró que no tenía nada que ver con el algoritmo y que su nombre no debía asociarse a él.