O Método de Ordenação Shell Short tem esse nome pois basicamente o algoritmo passa várias vezes pela lista, dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção, formando uma concha (shell).
Este método é, em geral, melhor que o método da bolha. Quanto mais ordenado estiver o vetor inicial, mais eficiente será a ordenação por inserção simples.
Observe que neste algoritmo o próprio vetor é utilizado no processo de ordenação, não consumindo, portanto, memória para a separação dos segmentos de vetor. Consome-se um pouco de memória somente para o armazenamento de variáveis de trabalho (auxiliares). Assim, o valor A[1] é comparado com A[h+1], A[2] com A[h+2], e assim por diante. Se h é grande, pode-se mover elementos que estão bastante afastados no vetor. O valor de h é diminuído a cada ciclo de ordenação, até atingir o valor 1 (neste caso, a ordenação se reduz a uma inserção simples).
O ideal é que a os valores de h sejam números primos entre si, de forma a garantir sobreposição de regiões de subdivisão.
Shell Short é o mais eficiente algoritmo de classificação dentre a complexidade quadrática.
Segue abaixo Ilustração do funcionamento do algoritmo ShellSort.
Abaixo o código fonte desse método…
void shell(int * v, int i) {
int x , j , valor;
int h = 1;
do {
h = 3*h+1;
} while(h< i);
do {
h /= 3;
for(x = h; x < i; x++) {
valor =v[x];
j = x – h;
while (j >= 0 && valor < v[j]) {
v [j + h] =v[j];
j -= h;
}
v [j + h] = valor;
}
} while ( h > 1);
}
SystEvolution 