Metodoshell

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 unosresultados 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 dosmotivos: 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 sesuele 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 mejoresresultados 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 quees 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 mejorresultados 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 encuanto 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...