Ordenación por el método de Shell (ShellSort)

Detalles: Categoría: Programación; Publicado el Domingo, 31 Agosto 2008 01:00

alt Siempre me ha fascinado el algoritmo de ordenacion de Shell. Debe su nombre al ingeniero y matemático estadounidense Donald Shell, que lo publicó en la revista Communications of the ACM en 1959.

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 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.

Intentaremos que en la medida de lo posible no sea demasiado pesado, utilizando ejemplos y animaciones.

CARACTERÍSTICAS

Bueno... ya hemos comentado algunas de ellas en la introducción.

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" 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.

(¿Alguno de los conceptos de éste apartado te es extraño? Consulta Algoritmos de ordenación).

EL FUNDAMENTO: la k-ordenación.

Imaginemos una lista de datos ordenables... por ejemplo, estos enteros:

74, 14, 21, 44, 38, 97, 11, 78, 65, 88, 30

Siempre se utilizan enteros para estos ejemplos porque es un tipo de dato sencillo, cómodo y estamos muy familiarizados con ellos... pero podrían ser datos de cualquier otro tipo, siempre y cuando tengamos un criterio de ordenación para compararlos. Cada uno de estos enteros, mantiene una posición en la lista (o array).

En el algoritmo de Inserción directa íbamos uno por uno, desde el segundo (14) al último (30) desplazando hacia la izquierda cada elemento hasta su posición entre los anteriores.

Bien... ya vimos que eso funcionaba relativamente bien... pero vamos a echar un vistazo intutivo a los datos. Fijémonos, por ejemplo, que los enteros están comprendidos entre el 11 (el más pequeño) y el 97 (el más grande) y que parecen más o menos uniformemente distribuidos.

Intuitivamente, podemos estar casi seguros de que el 97 estará por el final (muy a la derecha)... el 88 también... El 14 y el 11 estarán por el principio (muy a la izquierda) y parece sensato pensar que quizá el 44 o el 65 estarán mas o menos por la mitad.

Sin embargo, el algoritmo de Inserción, sistemáticamente "arrastrará" cada elemento comparándolo de uno en uno con los anteriores hasta encontrar su posición correcta.

Si fueramos capaces de "intutivamente" mover los elementos más grandes al final del array de un gran salto (con poco esfuerzo, pero también con poca precisión), los más pequeños al principio y los medianos los dejamos por enmedio no habríamos conseguido ordenar el array, pero si esa operación nos cuesta poco esfuerzo, una ordenación exhaustiva posterior también requeriría menos esfuerzo, porque cada elemento estaría cerca de su ubicación definitiva.

Imagina que te piden que en lugar de ordenar enteros, tienes que ordenar piedras... Si, si... piedras... por tamaño, con ayuda de una carretilla.

alt

Si aplicaras el algoritmo de Inserción directa tal cual harías muchas comparaciones y desplazamientos. Sin embargo, si colocas las que son más o menos pequeñas hacia el principio y las que son más gordas hacia el final, dejando las medianas por la mitad, no habrás conseguido ordenar las piedras todavía... pero las habrás dejado mucho más cerca de su ubicación definitiva. Ordenarlas ahora exhaustivamente supone menos esfuerzo.

alt

Esta es la idea básica del ShellSort: si podemos desplazar "a grosso modo" los elementos más grandes hacia el final y los más pequeños hacia el principio con poco esfuerzo, estaremos dejando cada elemento más cerca de su ubicación definitiva. Si finalmente aplicamos un método como InsertionSort, cada elemento se tendrá que desplazar pocos lugares.

Pedirle a un ordenador que haga algo intuitivamente es, de momento, bastante complicado, así que sustituiremos la intuición por un procedimento mecánico más o menos ingenioso.

Volvamos al array del principio.

74, 14, 21, 44, 38, 97, 11, 78, 65, 88, 30

Shell nos propone que hagamos sobre el array una serie de ordenaciones basadas en la inserción directa, pero dividiendo el array original en varios sub-arrays tales que cada elemento esté separado k elementos del anterior (a esta separación a menudo se le llama salto o gap)... Se debe empezar con k=n/2, siendo n el número de elementos de array, y utilizando siempre la división entera.... después iremos variando k haciéndolo más pequeño mediante sucesivas divisiones por 2, hasta llegar a k=1.

Pero vamos a ello... En nuestro ejemplo, n=11 (porque hay 11 elementos). Así que k=n/2=11/2=5

Empezamos con k=5. Así pues, vamos a dividir nuestro array original en 5 sub-arrays, en los cuales, sus elementos estarán separados por 5 lugares del array original (el salto o gap es 5).

Vamos a hacerlo con colores. Tomamos el primer elemento (el 74) contamos 5 lugares y tomamos también otro elemento (el 97) volvemos a contar 5 y tomamos otro (el 30) y acabamos porque se nos acaba el array.

El primer sub-array con k=5 es el formado por 74, 97 y 30. Vamos a pintarlos en rojo

74, 14, 21, 44, 38, 97, 11, 78, 65, 88, 30

Ahora, ordenaremos los elementos del sub-array rojo pero sólo entre ellos, utilizando el algoritmo de Inserción directa.

30, 14, 21, 44, 38, 74, 11, 78, 65, 88, 97

Fíjate qué curioso. El 30, un elemento relativamente pequeño se ha ido hacia el principio y el 97 hacia el final... ¡pero dando saltos (gap) de 5 en 5 lugares! Cada uno ha avanzado en saltos de 5 hacia una posición cercana a su ubicación definitiva.

Formemos ahora otro sub-array con salto k=5... partiendo del segundo elemento (el 14) y contando 5 (tomamos también el 11) y ya está, porque se acaba el array.

30, 14, 21, 44, 38, 74, 11, 78, 65, 88, 97

Vamos a ordenarlos entre ellos con Inserción directa... el 11 primero y el 14 después.

30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97

Ahora a por otro... el 21 y el 78

30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97

Están en orden entre ellos, así que se quedan como están.

Ahora le toca al sub-array formado por el 44 y el 65

30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97

Que también están en orden entre ellos... y finalmente el 38 y el 88, que también están en orden.

30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97

Hemos formado 5 sub-arrays en los cuales los elementos están separados por 5 lugares (porque k=5). Hemos ordenado cada sub-array por separado utilizando inserción directa, y hemos logrado que cada elemento se dirija hacia su ubicación definitiva en pasos de 5 lugares.

Por supuesto, no hemos terminado todavía, pero resulta evidente que algunos elementos, como el 30, el 97 o el 11 han dado un gran salto y que no deben andar muy lejos de su sitio final.

Decimos ahora que el array está 5-ordenado.

Para continuar con el algortimo, debemos ir reduciendo progresivamente k dividiéndolo sucesivamente por 2 y k-ordenando los subarrays que nos salgan (recuerda que nos salen k sub-arrays). Cuando lleguemos a k=1 habremos terminado.

Pero de momento, nuestra k valía 5, así que ahora k←k/2=5/2=2

Nuestra nueva k vale 2. Repetimos todo el tinglado, pero ahora nos saldrán 2 sub-arrays cuyos elementos están separados por 2 lugares.

El primero (en marrón) y el segundo (en verde):

30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97

Ordenamos por un lado los marrones entre ellos y los verdes entre ellos... es decir, 2-ordenamos el array (curiosamente, los verdes ya están ordenados.... probablemente ha contribuido a ello la 5-ordenacion que ya hemos hecho. En ese caso, la ordenación ha requerido muy poco esfuerzo)

14, 11, 21, 44, 30, 74, 38, 78, 65, 88, 97

Ahora, cada número está mucho más cerca de su posición definitiva... El array está 2-ordenado... pero sigue también 5-ordenado. No hemos perdido el trabajo que hicimos cuando k era 5.

Finalmente, calculamos un nuevo k diviendo el que tenemos entre 2. k←k/2=2/2=1

Hemos llegado a k=1. Cuando k es 1 sólo podemos obtener 1 sub-array cuyos elementos están separados 1 posición: el propio array original. Dicho de otra manera... cuando k es 1, el algoritmo de Shell se comporta exactamente igual que el de inserción directa sobre todo el array.

Sin embargo, las k-ordenaciones que hemos hecho (con k=5 y k=2) han hecho que cada elemento se aproximase con saltos de 5 y luego de 2 posiciones hacia su ubicación definitiva. Ahora que k=1 y que vamos a aplicar el algoritmo de inserción directa tal cual, haremos muchas menos comparaciones e intercambios que si lo hubieramos aplicado con en array tal como lo teníamos al empezar. El algoritmo de inserción directa se comporta tanto mejor cuanto más cerca está cada elemento de su sitio definitivo.

Finalmente, el array queda de ésta manera:

11, 14, 21, 30, 38, 44, 65, 74, 78, 88, 97

Cada elemento descolocado ha tenido que moverse pocos lugares. Muchos de ellos ni siquiera se han movido.

¿Todavía confus@? A ver si ésta animación de baja tecnología que hemos preparado te puede ayudar. En ella ordenamos 9 naipes de la baraja española: del AS al 9 de oros, utilizando el algoritmo de Shell.

(La música es Ragtime Dance, de Scott Joplin, obtenida de la página de Warren Trachtman. Gracias, Warren)

EL ALGORITMO

Con todo lo que ya sabemos, estamos en condiciones de aproximarnos a la obtención del algoritmo:

En primer lugar, sabemos que debemos empezar con k=n/2 (salto o gap de n/2) y luego obtener sucesivamente nuevos valores de k dividiéndolo por 2 hasta llegar a 1 (eso implica un bucle while, ya que sabemos que empezamos con k=n/2 y no terminamos mientras que k sea mayor o igual que 1)
Para cada valor de k (salto, gap) obtenido con el bucle anterior, debemos obtener k sub-arrays y ordenar con inserción directa cada uno de ellos (eso implica un bucle for, ya que sabemos exáctamente cuántos sub arrays debemos considerar: k)
Una vez que estemos considerando un sub-array, debemos ordenarlo con inserción directa. Si recordamos correctamente, el algoritmo de inserción directa recorría cada elemento del array a partir del segundo con un bucle for.
Finalmente, cada elemento del array (con Inserción directa) se iba comparando con los anteriores y desplazándolo -si procede- con un bucle while.

Así que tendremos un gran bucle while que estará pendiente de calcular k y de dejarnos salir después de que k sea 1. Dentro, un bucle for que se encargará de encontrar los k sub-arrays. Dentro de éste, otro bucle for (quizá podría ser un while también) encargado de ir seleccionando cada uno de los elementos del sub-array que consideramos desde el segundo hasta el último. Finalmente, y dentro de ese, un bucle while que compare cada elemento seleccionado con los anteriores del sub-array, para encontrar su lugar entre ellos.

Estos dos últimos bucles -los más interiores- son, en realidad, los bucles que realizan una inserción directa, pero adaptados para ordenar con saltos (gaps) de distancia k.

Vamos a ver si lo conseguimos.... Como de costumbre, vamos a utilizar C# como lenguaje.

Hemos implementado esos cuatros bucles. El código está comentado. Quizá fuera recomendable seguirlo con atención e incluso hacer algunas trazas ("a mano", desde luego) para acabar de entenderlo.

Una última puntualización: Éste algoritmo es correcto, y responde a la estructura que hemos comentado hasta ahora, pero difiere un poco del que se suele ver en los libros o en otras páginas de Internet... Échale un vistazo, y luego comentamos por qué el de los libros es algo distinto.

//Shell sort original con cuatro bucles
//Correcto, aunque no es la implementación más común
void ShellSort(int[] A)
{
   //el primer salto o gap (representado por la variable k)
   //es la mitad de la longitud del array
   int k=A.Length/2;
   //este primer bucle nos mantendrá dentro del algoritmo
   //mientras el salto sea mayor o igual que 1. Antes de
   //cada iteración dividimos el salto o gap (k) entre 2
   while (k>=1)
   {
     //este segundo bucle cuenta los subarrays que nos
     //salen para cada valor de salto k. 
     for (int subarray = 0; subarray < k; subarray++)
     {
       //para cada subarray recorremos sus elementos
       //con este otro bucle for, desde el segundo
       //hasta el último. Este bucle es igual que el del
       //algoritmo de inserción directa, pero adaptado
       //para un salto k
       for (int i = k+subarray; i < A.Length; i += k)
       {
         int v = A[i]; //tomamos el elemento i-ésimo
         int j = i - k; //apuntamos al anterior en el subarray
         //Con este bucle desplazamos elementos en el subarray
         //hasta encontrar la posición que le corresponde
         //al elemento i-ésimo que tenemos guardado en v
         //Es como el bucle interior de la inserción directa
         //pero adaptado para moverse por un subarray con
         //con salto k
         while (j >= 0 && A[j] > v)
         {
           A[j + k] = A[j];
           j-=k;
         }
         A[j + k] = v;
       } //fin for
     } //fin for
   //obtenemos un nuevo salto
   k /= 2;
   } //fin while
} //ShellSort

SIMPLIFICANDO

Pues como decíamos, si has encontrado éste algoritmo en otras páginas web o libros, probablemente te hayas dado cuenta de que suele implementarse con tres bucles en lugar de cuatro.

Bueno... nosotros hemos decidido empezar con cuatro, porque son los que se deducen de la explicación del algoritmo tal y como lo hemos planteado. Realmente, se puede reducir a tres bucles, aunque computacionalmente no ganamos nada: el algoritmo sigue haciendo exactamente los mismos pasos. Simplemente, el código fuente queda algo más compacto.

Esta simplificación se deduce del hecho de que entre los dos bucles "for" que tiene el algoritmo de arriba, lo que se consigue realmente es que el índice i vaya recorriendo todos los valores que hay desde k hasta A.Length (la longitud del array -excluido-)... pero i va tomando valores siguiendo los subarrays:

primero i vale k+0, 2k+0, 3k+0... para el primer subarray
Luego i vale k+1, 2k+1, 3k+1... para el siguente
... y así sucesivamente.

La cosa es que realmente i toma todos los valores comprendidos entre k y A.Length-1 (incluido)... pero dando saltos de tamaño k.

En cada iteración con i, lo que hacemos es colocar el elemento i-esimo en la posición correcta mediante inserción directa con saltos de tamaño k -eso lo hacemos con la variable j y la variable auxiliar v-.

Pero realmente, no hay ningún motivo que impida que i pueda tomar los valores comprendidos entre k y A.Length-1 de manera consecutiva: la variable j es la que debe dar saltos de tamaño k. La variable i no es necesario que lo haga.

Así pues, ambos dos bucles "for" pueden fundirse en uno solo... y esa es la implementación que se más se suele ver. No hemos empezado por ahí porque si lo hubieramos hecho, la explicación hubiera sido mucho menos intuitiva.

Vamos a ver como queda el algoritmo con esa simplificación: (insistimos de nuevo: computacionalmente, el algoritmo que sigue es equivalente al anterior... hace exactamente lo mismo, sólo que en otra secuencia algo menos intuitiva, y con un código fuente más compacto)

//Shell sort original pero con tres bucles
//en lugar de cuatro
//Esta es la implementación más común
//Es equivalente a la anterior, solo que más compacta
 
void ShellSort(int[] A)
{
   //el primer salto o gap (representado por la variable k)
   //es la mitad de la longitud del array
   int k = A.Length / 2;
   //este primer bucle nos mantendrá dentro del algoritmo
   //mientras el salto sea mayor o igual que 1. Antes de
   //cada iteración dividimos el salto o gap (k) entre 2
   while (k >= 1)
   {
     //este segundo bucle es el resultado de compactar los
     //dos bucles de la version anterior del algoritmo.
     //Logramos lo mismo (que i valga desde k hasta A.Lenght-1
     //pero en otra secuencia. 
     //Nos hemos quitado una variable de en medio: subarray
     for (int i=k; i<A.Length; i++)
     {
       int v = A[i]; //tomamos el elemento i-ésimo
       int j = i - k; //apuntamos al anterior en el subarray
       //Con este bucle desplazamos elementos en el subarray
       //hasta encontrar la posición que le corresponde
       //al elemento i-ésimo que tenemos guardado en v
       //Es como el bucle interior de la inserción directa
       //pero adaptado para moverse por un subarray con
       //con salto k
       while (j >= 0 && A[j] > v)
       {
         A[j + k] = A[j];
         j -= k;
       }
       A[j + k] = v;
     } //fin for
   k /= 2;
   } //fin while
} //ShellSort

OPTIMIZANDO

En todos los años que han pasado desde su publicación, mucha gente se ha dedicado al estudio de este algoritmo (ya lo comentábamos al principio). La secuencia original de saltos que propuso Donald Shell es la que hemos utilizado hasta ahora: empezamos con un salto k=n/2 (siendo n la longitud del array) y vamos dividiendo el salto sucesivamente por dos hasta finalizar con un salto k=1.

Un hecho curioso es que cualquier secuencia descendente de saltos hace que el algoritmo funcione también correctamente, siempre y cuando el último salto sea k=1. El hecho de terminar con k=1 hace que el algoritmo de Shell se comporte finalmente exactamente igual que el de Inserción directa, lo que garantiza que en última instancia, todo elemento llegue a su posición correcta.

Sin embargo, esto nos plantea una nueva cuestión ¿Existe una secuencia de saltos que proporcione, en general, mejores resultados que la propuesta originalmente?...

Pues realmente sí: de hecho, la propuesta original ni siquiera es una de las mejores.

Incluso, se ha podido demostrar que las secuencias geométricas (como ir dividiendo k por dos o por cualquier otro entero) no son buenas.

De esa manera, se ha podido llegar a otras secuencias que se comportan mejor. Ninguna de ellas es estrictamente geométrica.

El análisis de la complejidad del algoritmo utilizando esas secuencias es extremadamente complicado -y no necesariamente útil-, así que muchas de esas secuencias han sido obtenidas experimentalmente. Comparar unas con otras también es tarea complicada... así que simplemente, adaptaremos el algoritmo para utilizar una cualquiera de las muchas que hay propuestas.

Nos vamos a quedar con una de las más conocidas. La secuencia de saltos propuesta por Robert Sedgewick es la siguiente:

{1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1}

Lógicamente, debe terminar en 1. Empezaremos con el primer valor de la lista que sea menor que la longitud del array a ordenar... y seguiremos hasta llegar al 1.

Como ésta y otras muchas de estas secuencias no responden a una fórmula sencilla, lo mejor es utilizar un array para almacenar la secuencia. Haremos que k vaya tomando valores de ese array en sucesivas iteraciones del bucle exterior.

//Shellsort
//Siguendo la secuencia de Sedgewick
//En general, mejor que la secuencia original
void ShellSort(int[] A)
{
   //la secuencia de saltos de Sedgewick
   //Puede ser sustituida por cualquier otra, siempre y
   //cuando el último valor sea un 1
   int[] gaps ={1391376, 463792, 198768, 86961, 33936, 13776,
                4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1};
   //utilizamos un índice para movernos por la secuencia.
   //nos colocamos al principio.
   int indiceGap = 0;
   //el primer salto o gap (representado por la variable k)
   //es el mayor valor del array gaps que sea menor que la 
   //longitud de nuestro array a
   while (gaps[indiceGap] > A.Length)
   {
      indiceGap++;
   };
 
   //este primer bucle nos mantendrá dentro del algoritmo
   //mientras el salto sea mayor o igual que 1. Es decir,
   //mientras no hayamos agotado los saltos del array gaps
   while (indiceGap < gaps.Length)
   {
     //Tomamos el valor del salto en esta iteración
     int k = gaps[indiceGap];
 
     //Nos metemos en la k-ordenación
     for (int i=k; i<A.Length; i++)
     {
       int v = A[i]; 
       int j = i - k; 
       while (j >= 0 && A[j] > v)
       {
          A[j + k] = A[j];
          j -= k;
       }
       A[j + k] = v;
     } //fin for
   //pasamos al siguiente valor de salto
   indiceGap++;
   } //fin while
} //ShellSort

Para comprobar que, en efecto, la secuencia de Sedgewick se comporta mejor que la original de Shell hemos hecho algunas pruebas. Hemos hecho pruebas con arrays de enteros rellenos de números aleatoriamente, y hemos pasado el algoritmo con la secuencia original y el que tiene la secuencia de Sedgewick, y hemos contado el número de intercambios que ha realizado cada uno. Los resultados han sido estos (redondeando a dos dígitos significativos para no marear):

Tamaño	Intercambios Shell	Intercambios Sedgewick
1000	8800	7500
5000	61000	53000
10000	150000	120000
30000	520000	460000
100000	2700000	1700000
500000	18 millones	9 millones
1 millón	44 millones	17 millones
5 millones	270 millones	99 millones
10 millones	640 millones	220 millones

No es que demuestre nada, pero los resultados son bastante significativos.

Conclusiones:

Este es un algoritmo eficaz, relativamente eficiente en la mayoría de los casos, fácil de implementar, no consume memoria extra dinámicamente y se comporta bastante bien para unos datos de entrada de mediano tamaño.

Por último, todo esto está muy bien... pero yo he utilizado este algoritmo para ordenar enteros ¿Se puede utilizar para ordenar Objetos u otro tipo de datos?

Pues sí... sin ningún problema, pero hay que adaptarlo un poco. Primero, necesitamos tener un criterio claro de ordenación, y que algún método nos permita saber dados dos objetos cualesquiera si están en orden o no. Mira cómo lo hicimos con el algoritmo de la burbuja. Lo mismo se puede aplicar al algoritmo de Shell.

Para saber más:

ShellSort en la Wikipedia (en inglés)
Análisis de ShellSort en la Flensburg University of Applied Sciences