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)<br />
{<br />
   int kmenor = vetor[0];<br />
   int kmaior = vetor[tamanho - 1];<br />
   int den = kmaior - kmenor;<br />
   int cte1 = (kmaior - (tamanho - 1) * kmenor) / den;<br />
   int cte2 = (tamanho - 2) / den;</p>
<p>   int end = cte1 + chave * cte2;</p>
<p>   if(chave != vetor[end])<br />
   {<br />
      if(chave &lt; vetor[end])<br />
         while(end &gt; 0 &amp;&amp; chave &lt; vetor[end])<br />
            end--;<br />
      else<br />
         while(end &lt; tamanho - 1 &amp;&amp; chave &gt; vetor[end])<br />
            end++;<br />
   }</p>
<p>   if(end &gt;= 0 &amp;&amp; end &lt; tamanho &amp;&amp; chave == vetor[end])<br />
      return end;</p>
<p>   return -1;<br />
}


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)<br />
{<br />
   int i, j, menor, aux;</p>
<p>   for(i = 0; i &lt; tamanho - 1; ++i)<br />
   {<br />
      menor = i;<br />
      for(j = i + 1; j &lt; tamanho; ++j)<br />
      {<br />
         if(vetor[j] &lt; vetor[menor])<br />
            menor = j;<br />
      }<br />
      aux = vetor[i];<br />
      vetor[i] = vetor[menor];<br />
      vetor[menor] = aux;<br />
   }<br />
}