2.4 Shell Sort
Shell Sort es un algoritmo de ordenamiento basado en inserción, pero optimizado para trabajar de forma más eficiente en listas grandes. Fue propuesto por Donald Shell en 1959 y es considerado una mejora significativa del algoritmo de Insertion Sort. Su ventaja radica en que comienza ordenando elementos separados por grandes intervalos y, progresivamente, reduce esos intervalos, acercando los elementos a su posición final antes de realizar un ordenamiento final más fino.
Shell Sort toma una lista y comienza ordenando elementos que están separados por cierta distancia gap, formando sublistas implícitas. A medida que el algoritmo avanza, va reduciendo ese gap, y los elementos se vuelven a ordenar hasta llegar a un gap de 1, en el cual se realiza una inserción final sobre una lista que ya está casi ordenada.
Este enfoque logra mejorar considerablemente el rendimiento de Insertion Sort para listas grandes, donde Insertion Sort tendría un costo cuadrático.
El secreto está en el presort. Aunque la última fase de Shell Sort es un Insertion Sort completo, al haber “acercado” previamente los elementos a su posición final, la inserción es mucho más rápida. En lugar de tener que mover elementos desde el final al principio, ya están casi ordenados. Esto permite que el rendimiento se aproxime a O(n) en esa última pasada.
Vamos a ordenar la siguiente lista utilizando sublistas iniciales con sólo dos y tres elementos. Determinamos los elementos de cada sublistas estableciendo un valor de separación entre los subíndices de cada sublista. Más adelante explicaremos cómo elegimos los valores de separación. Utilizaremos un espacio inicial de 7
Un espacio de 7 significa que la primera sublista tiene los subíndices 0, 7, 14 (valores de elemento 40, 75, 57, mostrados en color claro); la segunda sublista tiene los subíndices 1, 8, 15 (valores de elemento 35, 55, 65, mostrados en color oscuro); la tercera sublista tiene los subíndices 2, 9 (valores de elemento 80, 90, mostrados en gris); y así sucesivamente. Hay siete sublistas
Comenzamos el proceso insertando el valor en la posición 7 (valor del hueco) en su sublista (elementos en 0 y 7). A continuación, insertamos el elemento en la posición 8 en su sublista (elementos en 1 y 8). Continuamos hasta que hemos insertado el último elemento (en la posición 15) en su sublista (elementos en 1, 8 y 15). El resultado de realizar la ordenación por inserción en todas las siete sublista con dos o tres elementos es el siguiente
A continuación utilizamos un hueco de 3. Sólo hay tres sublistas, y la más larga tiene seis elementos. La primera sublista tiene los subíndices 0, 3, 6, 9, 12, 15; la segunda sublista tiene los subíndices 1, 4, 7, 10, 13; la tercera sublista tiene los subíndices 2, 5, 8, 11, 14.
Comenzamos el proceso insertando el elemento en la posición 3 (valor del hueco) en su sublista. A continuación, insertamos el elemento en la posición 4, y así sucesivamente. El resultado de todas las inserciones es el siguiente
Por último, utilizamos una separación de 1, que realiza una ordenación por inserción en todo el array. Debido a la preordenación, se necesitará 1 comparación para insertar 34, 1 comparación para insertar 45 y 60, 3 comparaciones para insertar 35, 2 comparaciones para insertar 55, 1 comparación para insertar 62, 2 comparaciones para insertar 57, 2 comparaciones para insertar 60, y sólo 1 comparación para insertar cada uno de los valores restantes.
procedure shellSort(A: lista de n elementos)
gap ← n / 2
mientras gap > 0 hacer
para i desde gap hasta n-1 hacer
temp ← A[i]
j ← i
mientras j ≥ gap y A[j - gap] > temp hacer
A[j] ← A[j - gap]
j ← j - gap
A[j] ← temp
gap ← floor(gap / 2.2)
fin procedimiento
| Caso | Comparaciones | Complejidad |
|---|---|---|
| Mejor caso | Lista casi ordenada | O(n log n) |
| Peor caso | Depende del gap | O(n²) (clásico) |
| Promedio | (con Hibbard) | O(n^3/2) |
La eficiencia de Shell Sort depende en gran medida de la selección de la secuencia de gaps. Algunas secuencias recomendadas:
-
Hibbard: 1, 3, 7, 15, ...
-
Sedgewick: combinación de potencias de 2 y 3
-
Knuth: (3^k - 1) / 2
-
Empírica:
n / 2, n / 2.2, ..., 1(muy usada)
-
No estable.
-
In-place (no usa memoria adicional significativa).
-
Ideal para listas de tamaño medio.
-
Mucho más rápido que Insertion Sort para listas grandes.
-
Fácil de implementar.
-
No se utiliza en librerías estándar modernas, pero tiene valor pedagógico y aplicaciones prácticas en sistemas embebidos o juegos.
El algoritmo fue presentado por Donald Shell en 1959 en su artículo A High-Speed Sorting Procedure publicado en Communications of the ACM. Desde entonces, se ha convertido en una referencia clásica dentro de los métodos de ordenamiento intermedios: ni tan simples como Bubble Sort ni tan sofisticados como Merge o Quick Sort.
Shell Sort se utiliza cuando:
-
Se necesita un algoritmo simple pero más eficiente que Insertion Sort.
-
No se dispone de suficiente espacio para implementar Merge Sort.
-
Se trabaja en sistemas embebidos, juegos o microcontroladores donde se prioriza bajo uso de memoria.
Por ejemplo, puede emplearse en videojuegos para ordenar enemigos por distancia de forma eficiente con bajo consumo de recursos, o en sistemas de control donde se debe realizar una ordenación rápida con bajo overhead.
void shellSort(std::vector<int>& vec) {
int n = vec.size();
int gap = n / 2;
while (gap > 0) {
for (int i = gap; i < n; i++) {
int temp = vec[i];
int j = i;
while (j >= gap && vec[j - gap] > temp) {
vec[j] = vec[j - gap];
j -= gap;
}
vec[j] = temp;
}
gap = static_cast<int>(gap / 2.2); // Reducción empírica
}
}