Estrutura

Shell Sort
Criado por Donald Shell em 1959, publicado pela Universidade de Cincinnati, Shell sort é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta.O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles. 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.
Esse algoritmo é uma extensão do algoritmo da inserção direta (Ronald L. Shell, 1959). A diferença com relação à inserção direta é o número de segmentos do vetor. Na inserção direta é considerado um único segmento do vetor onde os elementos são inseridos ordenadamente. No método do Shell são considerados diversos segmentos.
A ordenação é realizada em diversos passos. A cada passo está associado um incremento I, o qual determina os elementos que pertencem a cada um dos segmentos:

segmento 1 - vet[1], vet[1 + I], vet[1 + 2I], ... segmento 2 - vet[2], vet[2 + I], vet[2 + 2I], ...
...
segmento k - vet[k], vet[k + I], vet[k + 2I], ...

A cada passo todos os elementos (segmentos) são ordenados isoladamente por inserção direta. No final de cada passo o processo é repetido para um novo incremento I igual a metade do anterior, até que seja executado um passo com incremento I = 1. O valor do incremento I é sempre uma potência inteira de 2. O valor do incremento inicial é dado por 2 ** NP, onde NP é o número de passos para ordenar o vetor (fornecido pelo usuário, NP é uma aproximação inicial).

Assim, para NP = 3 o valor do incremento em cada passo seria:
I = 2**3 = 8
I = 2**2 = 4
I = 2**1 = 2
I = 2**0 = 1

Aplicando inserção direta em cada segmento. Nesse último passo os elementos estão próximos das suas posições finais, o que leva a um menor número de