Algoritmos de Busca #4 – Busca Direta Transformada

Padrão


Temos aqui outro algoritmo de busca, chamado de Busca Direta Transformada. Dos algoritmos de busca apresentados até agora, este é o que possui o melhor desempenho.

Segue a implementação do algoritmo em C:

int buscaDiretaTransformada(int *vetor, int chave, int tamanho)
{
   int kmenor = vetor[0];
   int kmaior = vetor[tamanho - 1];
   int den = kmaior - kmenor;
   int cte1 = (kmaior - (tamanho - 1) * kmenor) / den;
   int cte2 = (tamanho - 2) / den;

   int end = cte1 + chave * cte2;

   if(chave != vetor[end])
   {
      if(chave < vetor[end])
         while(end > 0 && chave < vetor[end])
            end--;
      else
         while(end < tamanho - 1 && chave > vetor[end])
            end++;
   }

   if(end >= 0 && end < tamanho && chave == vetor[end])
      return end;

   return -1;
}


Algoritmos de Ordenação #2 – Seleção Direta

Padrão


Continuando com os algoritmos de ordenação, temos uma implementação em C do algoritmo de ordenação chamado Seleção Direta (ou Selection Sort). Esse algoritmo baseia-se em passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.

Segue, então, a minha implementação deste algoritmo em C:

void selecaoDireta(int *vetor, int tamanho)
{
   int i, j, menor, aux;

   for(i = 0; i < tamanho - 1; ++i)
   {
      menor = i;
      for(j = i + 1; j < tamanho; ++j)
      {
         if(vetor[j] < vetor[menor])
            menor = j;
      }
      aux = vetor[i];
      vetor[i] = vetor[menor];
      vetor[menor] = aux;
   }
}