Método Shell Short

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);

}