Algoritmos de Ordenação #4 – Shell Sort

Padrão


Temos aqui a implementação do algoritmo Shell Sort. Criado por Donald Shell em 1959, publicado pela Universidade de Cincinnati, o Shell Sort é o mais eficiente algoritmo de ordenação dentre os de complexidade quadrática (não utiliza recursividade). É 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 vetor 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 (algoritmo já mostrado no blog).

Segue a implementação em C do algoritmo:

void shellSort(int *vetor, int tamanho)<br />
{<br />
   int i = (tamanho - 1) / 2;<br />
   int chave, k, aux;</p>
<p>   while(i != 0)<br />
   {<br />
      do<br />
      {<br />
         chave = 1;<br />
         for(k = 0; k &lt; MAX - i; ++k)<br />
         {<br />
            if(Vetor[k] &gt; Vetor[k + i])<br />
            {<br />
               aux = Vetor[k];<br />
               Vetor[k] = Vetor[k + i];<br />
               Vetor[k + i] = aux;<br />
               chave = 0;<br />
            }<br />
         }<br />
      }while(chave == 0);<br />
      i = i / 2;<br />
   }<br />
}