método de Shell

El método de ordenamiento Shell consiste en dividir el arreglo (o la lista de elementos) en intervalos (o bloques) de varios elementos para organizarlos después por medio del ordenamiento de inserción directa. El proceso se repite, pero con intervalos cada vez más pequeños, de tal manera que al final, el ordenamiento se haga en un intervalo de una sola posición, similar al ordenamiento por inserción directa, la diferencia entre ambos es qué, al final, en el método ShellSu nombre proviene de su creador, Donald Shell, y no tiene que ver en la forma como funciona el algoritmo. los elementos ya están casi ordenados. Existen varias formas de calcular el intervalo, lo cual puede mejorar la efectividad del algoritmo. A continuación, explicaremos la secuencia original propuesta por Shell: n/2, n/4…, n/n, es decir, uno (dividir entre dos, hasta que el último intervalo sea uno), donde n es el tamaño del arreglo.

ejemplo

#include <vector>

 int n = arr.size();

 // Calculamos el tamaño de salto inicial (gap)

 int gap = n / 2;

 // Realizamos el algoritmo de ordenación Shell

 while (gap > 0) { 

 for (int i = gap; i < n; ++i) { 

 int temp = arr[i];

 int j = i;

 // Realizamos la inserción en la sublista correspondiente 

 while (j >= gap && arr[j - gap] > temp) { 

 arr[j] = arr[j - gap]; 

 j -= gap; 

 }

 arr[j] = temp; 

 }