Metodo de ordenamiento Shell Sort

Metodo de ordenamiento Shell Sort

Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección directa o el de inserción directa.

Aunque a menudo, es un algoritmo un tanto olvidado por dos motivos: en primer lugar, en los cursos básicos de programación se suele pasar por alto o se pasa «de puntillas» por este algoritmo, dado que su comprensión requiere un cierto esfuerzo y algo de tiempo, y se suele centrar la atención en los tres algoritmos más básicos (burbuja, selección e inserción); y en segundo lugar, el algoritmo QuickSort, desarrollado por Tony Hoare en 1962 puede dar mejores resultados aún que éste, con lo cual, le suele hacer bastante sombra en los temarios de los cursos de programación básicos.

Sin embargo, es necesario romper una lanza a favor del algoritmo ShellSort, ya que es el mejor algoritmo de ordenación in-situ… es decir, el mejor de aquellos en los que la cantidad de memoria adicional que necesita -aparte de los propios datos a ordenar, claro está- es constante, sea cual sea la cantidad de datos a ordenar. El algortimo de la burbuja, el de selección directa, el de inserción directa y el de Shell son todos in-situ, y éste último, el de Shell, es el que mejor resultados da, sin ninguna duda de todos ellos y sus posibles variantes.

Por supuesto que otros métodos de ordenación, como QuickSort, BinSort, HeapSort o RadixSort pueden pueden superar a ShellSort en cuanto al tiempo de ejecución, pero ninguno de ellos es ya un algoritmo in-situ. En todos ellos es necesario gestionar una cantidad adicional de memoria proporcional al tamaño de los datos a ordenar… pero de ellos hablaremos en otros artículos.

En este artículo nos centraremos en ShellSort. Describiremos la idea que subyace detrás del algoritmo, la k-ordenación, e intentaremos llegar de manera intuitiva al código del algorimo. Finalmente, intentaremos hablar de alguna simplificación y optimización del algoritmo. Todo ello, sin meternos en el berenjenal de demostrar su corrección.

Características:

• Se trata de un algoritmo de ordenación interna. Al igual que cualquier otro de ordenación interna (los datos están en memoria principal) podría utilizarse para ordenación externa (en memoria secundaria) siempre y cuando se disponga de acceso aleatorio, pero el algoritmo no fue ideado para eso.
• Se basa en comparaciones e intercambios.
• Necesita que el tiempo de acceso a cualquier dato sea constante (es decir, fue ideado para trabajar con arrays, arrays de referencias o punteros, etc…). Ojo a otras estructuras, como listas enlazadas, etc… ya que en ese caso, el tiempo de acceso a un elemento no es constante, depende de la posición del elemento.
• No es estable: dados dos elementos que al compararlos sean «iguales» -es decir, que pueden ir indistintamente en la misma posición, no mantienen necesariamente el orden relativo inicial entre ellos.
• El estudio de su complejidad no es trivial, sino todo lo contrario. La implementación original de Shell tiene una complejidad en el peor caso de O(n²), aunque en un caso promedio o en casos típicos comprobados empíricamente, los resultados son mucho mejores que con la burbuja, selección directa o inserción directa, cuya complejidad en el peor caso también es del orden de O(n²).
• Sin embargo, optimizaciones posteriores han logrado reducir esa cota… Por ejemplo, con la optimización de Robert Sedgewick se llega a O(n^4/3), y con la propuesta por Vaughan Pratt se llega al orden de O(n log₂n).
• En 1992, Greg Plaxton, Bjorn Poonen y Torsten Suel prueban que es posible incluso rebajar aún más esas cotas.
• En cierto modo, puede considerarse una ampliación del algortimo de inserción directa, con lo cual, conviene tenerlo claro antes de meterse con el de Shell.
• No es un algoritmo en-línea.

Aca les va el apoyo multimedia :