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)
{
   int i = (tamanho - 1) / 2;
   int chave, k, aux;

   while(i != 0)
   {
      do
      {
         chave = 1;
         for(k = 0; k < MAX - i; ++k)
         {
            if(Vetor[k] > Vetor[k + i])
            {
               aux = Vetor[k];
               Vetor[k] = Vetor[k + i];
               Vetor[k + i] = aux;
               chave = 0;
            }
         }
      }while(chave == 0);
      i = i / 2;
   }
}


2 comentários sobre “Algoritmos de Ordenação #4 – Shell Sort

    • Marcus Vinicius Graciano

      Ninguem respondeu o coitado.
      Para os próximos que chegarem aqui e tiverem a mesma dúvida, neste caso o MAX é uma constante( definida previamente), que corresponde ao tamanho do seu vetor.

Deixe uma resposta